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

Solution

The first idea is to DFS every entry in the matrix, and see how long an increasing sequence can be made.

An increasing sequence must satisfy its next element shall greater than its current element. Base on this understanding, we can make a recursive function for calculating the longest increasing sequence from a certain entry. And if the next value is greater than the current, we can call this function for the next elements. We also notice that there might have a redundant computation for the same entry, so we use memorization to reduce it.

  int max = 0;
    int m = 0;
    int n = 0;
    int[][] result;
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        if(m == 0 && n == 0) return 0;
        result = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++) {
                result[i][j] = -1;
            }
        }
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                max = Math.max(max, helper(matrix, i, j));
            }
        }
        return max;
    }
    
    int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int helper(int[][] matrix, int i, int j) {
        
        if(result[i][j] != -1) return result[i][j];
        int ret = 1;
        for(int[] dir : dirs){
            int newi = i + dir[0];
            int newj = j + dir[1];
            if(newi >= m || newi < 0 || newj >= n || newj < 0) continue;
            if(matrix[i][j] < matrix[newi][newj]) {
                ret = Math.max(ret, 1 + helper(matrix, i + dir[0], j + dir[1]));
            }
        }
        result[i][j] = ret;
        return ret;
    }