329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: 
nums = 
[
  [
9
,9,4],
  [
6
,6,8],
  [
2
,
1
,1]
] 

Output:
 4 

Explanation:
 The longest increasing path is 
[1, 2, 6, 9]
.

Example 2:

Input:
 nums = 
[
  [
3
,
4
,
5
],
  [3,2,
6
],
  [2,2,1]
] 

Output: 
4 

Explanation: 
The longest increasing path is 
[3, 4, 5, 6]
. Moving diagonally is not allowed.

Solution

(1) Java

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (memo[i][j] == 0) {
                    helper(matrix, i, j, memo, new boolean[m][n]);
                } 
            }
        }
        int rst = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rst = Math.max(rst, memo[i][j]);
            }
        }
        return rst;
    }

    private int helper(int[][] matrix, int i, int j, int[][] memo, boolean[][] visited) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        visited[i][j] = true;
        int rst = 0;
        if (i-1 >= 0 && !visited[i-1][j] && matrix[i-1][j] > matrix[i][j]) {
            rst = Math.max(rst, helper(matrix, i-1, j, memo, visited));
        }
        if (i+1 < matrix.length && !visited[i+1][j] && matrix[i+1][j] > matrix[i][j]) {
            rst = Math.max(rst, helper(matrix, i+1, j, memo, visited));
        }
        if (j-1 >= 0 && !visited[i][j-1] && matrix[i][j-1] > matrix[i][j]) {
            rst = Math.max(rst, helper(matrix, i, j-1, memo, visited));
        }
        if (j+1 < matrix[0].length && !visited[i][j+1] && matrix[i][j+1] > matrix[i][j]) {
            rst = Math.max(rst, helper(matrix, i, j+1, memo, visited));
        }
        visited[i][j] = false;
        memo[i][j] = rst+1;
        return memo[i][j];
    }
}

(2) Python

(3) Scala