329. Longest Increasing Path

Longest Increasing Path

/**

 * 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].

 *

 * IMP-2: Common question.

 */

Below is a simple approach to traverse each cell in the matrix once via dfs and storing the maximum path length from that cell into an array that can be later referenced to return the maximum path from that cell onwards without having to rerun the entire dfs (this concept is called memorization).

I have another non intuitive but equally fast solution in github code which for each cell calculates the number of neighboring cells that are greater than it (outdegree) and then traverses the array from lowest outdegree to the highest outdegree via topological sort. The depth of the traversal identifies the longest sequence length. I am not explaining that solution here but recommend that you have a look at the code and draw out the verification of the solution on a white board.

Here is the link to the code on github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/hard/LongestIncreasingPath.java

Logic is:

1. Create a two-dimensional array to identify the matrix.
2. The array will be initialized with 0s which we will use as a sentinel.
3. For each cell if neighbor is greater than current cell
   1. Recurse into neighbor
   2. If index of cell in array created in 1 is non zero then it means that the cell has been already processed. In this case simply return the cell value.
   3. If index of cell in array created in point 1 above is 0 then it means that index is yet to be processed, so process its count and return increasing sequence length from the given index.
   4. Increasing path incremental can be done simply as
      1. Getting the max path length from traversing each of the directions
      1. Adding 1 to that for the current cell

Here is the code:

public int longestIncreasingPath(int[][] matrix) {
    if (matrix.length == 0) return 0;
    m = matrix.length; n = matrix[0].length;
    int[][] cache = new int[m][n];
    int ans = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            ans = Math.max(ans, dfs(matrix, i, j, cache));
    return ans;
}

private int dfs(int[][] matrix, int i, int j, int[][] cache) {
    if (cache[i][j] != 0) return cache[i][j];
    for (int[] d : dirs) {
        int x = i + d[0], y = j + d[1];
        if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
            cache[i][j] = Math.max(cache[i][j], dfs(matrix, x, y, cache));
    }
    return ++cache[i][j];
}