Longest Increasing Path in a Matrix

NeetCode: Longest Increasing Path in a Matrix · LeetCode: 329. Longest Increasing Path in a Matrix · Difficulty: Hard

Given an m x n integer matrix (int[][]), return the length of the longest strictly increasing path. From each cell you may move up, down, left or right (not diagonally, and not outside the grid).

Example

Text

Input:  matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]    Output: 4   (1 -> 2 -> 6 -> 9)
Input:  matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]    Output: 4   (3 -> 4 -> 5 -> 6)

Brute force: DFS from every cell

Start a depth-first search at every cell and only step to strictly larger neighbours. Because values must strictly increase, a path can never revisit a cell, so no visited set is needed. Many different paths run through the same cell, and each DFS re-explores everything reachable from it. On grids with many increasing routes (for example a smooth gradient) the number of explored paths is exponential.

Java

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private int dfs(int[][] m, int r, int c) {
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m.length || nc >= m[0].length) {
                continue;
            }
            if (m[nr][nc] > m[r][c]) {
                best = Math.max(best, 1 + dfs(m, nr, nc));
            }
        }
        return best;
    }

    public int longestIncreasingPath(int[][] matrix) {
        int best = 0;
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[r].length; c++) {
                best = Math.max(best, dfs(matrix, r, c));
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestIncreasingPath(new int[][] {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
        System.out.println(sol.longestIncreasingPath(new int[][] {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
        System.out.println(sol.longestIncreasingPath(new int[][] {{1}}));
    }
}

Output

4
4
1

Time: exponential in the worst case. Space: O(m · n) for the recursion depth.

Optimal: DFS with memoisation

Define longest(r, c) as the length of the longest increasing path that starts at (r, c). It equals 1 + max(longest(neighbour)) over strictly larger neighbours, and it depends on nothing but the cell itself. That makes it a DP over m * n states, and because the "strictly larger" relation has no cycles, plain recursion with a cache is a valid evaluation order. Each cell is solved once and looks at four neighbours.

Java

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private int dfs(int[][] m, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) {
            return memo[r][c];
        }
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m.length || nc >= m[0].length) {
                continue;
            }
            if (m[nr][nc] > m[r][c]) {
                best = Math.max(best, 1 + dfs(m, nr, nc, memo));
            }
        }
        memo[r][c] = best;
        return best;
    }

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[][] memo = new int[matrix.length][matrix[0].length]; // 0 means not computed
        int best = 0;
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                best = Math.max(best, dfs(matrix, r, c, memo));
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestIncreasingPath(new int[][] {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
        System.out.println(sol.longestIncreasingPath(new int[][] {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
        System.out.println(sol.longestIncreasingPath(new int[][] {{1}}));
        System.out.println(sol.longestIncreasingPath(new int[][] {}));
    }
}

Output

Time: O(m · n). Space: O(m · n).

The recursion depth can reach the path length, up to m * n. Deep recursion on the Java thread stack can throw StackOverflowError on a large grid, so the small examples here are safe but a worst-case grid is better run on a thread with a larger stack or with the topological version. An alternative that avoids deep recursion is to peel off cells layer by layer in topological order (Kahn's algorithm), with the same complexity.