220. Longest Increasing Path in a Matrix

The longest increasing path starting at a cell depends only on its strictly-greater neighbours, and the grid has no cycles when moving strictly upward — so each cell's answer can be memoized and reused.

Why memoization works

Moving only to a strictly greater neighbour means the path can never revisit a cell (values strictly increase), so the 'graph' of moves is a DAG. dfs(r, c) = length of the longest increasing path starting at (r, c). Once computed it never changes, so cache it in memo[r][c].

DFS

dfs(r, c):
    if memo[r][c]: return memo[r][c]
    best = 1
    for each neighbour with value > matrix[r][c]:
        best = max(best, 1 + dfs(neighbour))
    memo[r][c] = best
    return best
answer = max over all cells of dfs(r, c)

Worked example

[[9,9,4],[6,6,8],[2,1,1]]: the path 1 → 2 → 6 → 9 has length 4, the longest.

Complexity

• Time: O(m·n) — each cell's path length computed once.
• Space: O(m·n) for the memo table and recursion.

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

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

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