329 Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

1. Question

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:

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

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

Example 2:

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

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

2. Implementation

(1) DFS + memoinzation

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int maxLen = 1;

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = getLengthOfIncreasingPath(i, j, matrix, cache, directions);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }

    public int getLengthOfIncreasingPath(int row, int col, int[][] matrix, int[][] cache, int[][] directions) {
        if (cache[row][col] != 0) {
            return cache[row][col];
        }

        int curMaxLen = 1;

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(row, col, nextRow, nextCol, matrix)) {
                int len = 1 + getLengthOfIncreasingPath(nextRow, nextCol, matrix, cache, directions);
                curMaxLen = Math.max(curMaxLen, len);
            }
        }

        cache[row][col] = curMaxLen;
        return curMaxLen;
    }

    public boolean isValid(int curRow, int curCol, int nextRow, int nextCol, int[][] matrix) {
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[curRow][curCol] < matrix[nextRow][nextCol];
    }
}

3. Time & Space Complexity

DFS + memoinzation: 时间复杂度O(mn)，空间复杂度O(mn)