329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

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

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[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.

Example 3:

Input: matrix = [[1]]
Output: 1

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 200

• 0 <= matrix[i][j] <= 231 - 1

My Solutions:

class Solution {
    int m, n;
    int[][] cache; // record the largest number of steps at each grid
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 4 directions, up, right, down, left
    int max = 1; // max step should be at least 1
    
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        m = matrix.length;
        n = matrix[0].length;
        cache = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = dfs(matrix, i, j);
            }
        }
        return max;
    }
    
    public int dfs(int[][] matrix, int i, int j) {
        if (cache[i][j] != 0) return cache[i][j]; // current grid has been visited
        int res = 1;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            // iterate each grid in the matrix
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
                res = Math.max(res, dfs(matrix, x, y) + 1);
        }
        cache[i][j] = res;
        max = Math.max(max, res);
        return res;
    }
}

也可以只用dfs helper function循环每个格子，在longestIncreaingPath里记录最大值，但不知道为什么速度比较慢。

class Solution {
    
    int m;
    int n;
    int[][] cache;
    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        m = matrix.length;
        n = matrix[0].length;
        
        cache = new int[m][n];
        
        int max = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int temp = dfs(matrix, i, j);
                max = Math.max(temp, max);
            }
        }
        return max;
    }
    
    private int dfs(int[][] matrix, int i, int j) {
        if (cache[i][j] != 0) return cache[i][j];
        int max = 1;
        for (int[] d : dir) {
            int x = i + d[0];
            int y = j + d[1];
            if (x < 0 || x >= m || y < 0 || y >=n || matrix[x][y] <= matrix[i][j]) continue;
            int temp = 1 + dfs(matrix, x, y);
            max = Math.max(temp, max);
        }
        cache[i][j] = max;
        return max;
    }
}