Longest Increasing Path in a Matrix

Hard2D Grid DP · DFS + Memoization🧩 Grid DP LeetCode #329 ↗Updated Oct 30, 2026

Problem

Given an m × n integer grid, find the length (number of cells) of the longest path in which every step goes up, down, left or right to a cell with a strictly larger value. Diagonal moves and wrapping around the border are not allowed.

Input[[9,9,4],[6,6,8],[2,1,1]]Output4 (1→2→6→9)

Input[[3,4,5],[3,2,6],[2,2,1]]Output4 (3→4→5→6)

Input[[1]]Output1

1 ≤ m, n ≤ 200 · 0 ≤ matrix[i][j] ≤ 2³¹-1

Try it yourself

Java

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because each step must go strictly uphill, a path can never revisit a cell — the grid is a DAG. So “longest path starting at (r,c)” is a fixed number: compute it once, cache it, reuse it.

PatternGrid DP

Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.

Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.

Open the Grid DP guide →

Approaches

Brute ForcePlain DFS from Every Cell

Time O(mn·3^L)Space O(mn)

From each cell, recursively try all four larger neighbours and keep the best path length. No visited set is needed since values strictly increase. Each call branches up to 3 ways (it can't step back downhill) for up to L levels (L = answer), so the same sub-paths are re-explored again and again.

Java

private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int longestIncreasingPath(int[][] matrix) {
    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));
    return best;
}
private int dfs(int[][] a, int r, int c) {
    int len = 1;
    for (int[] d : DIRS) {
        int x = r + d[0], y = c + d[1];
        if (x >= 0 && x < a.length && y >= 0 && y < a[0].length && a[x][y] > a[r][c])
            len = Math.max(len, 1 + dfs(a, x, y));
    }
    return len;
}

Correct, but exponential in the path length — times out on large grids.

BetterSort Cells by Value + DP

Time O(mn log(mn))Space O(mn)

Process cells from the largest value down. When we reach a cell, every strictly larger neighbour is already final, so dp[cell] = 1 + max(dp[larger neighbour]) (or 1). Sorting supplies a valid topological order of the DAG.

Java

private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, best = 0;
    Integer[] cells = new Integer[m * n];
    for (int k = 0; k < m * n; k++) cells[k] = k;
    Arrays.sort(cells, (p, q) -> Integer.compare(matrix[q / n][q % n], matrix[p / n][p % n]));
    int[][] dp = new int[m][n];
    for (int k : cells) {
        int r = k / n, c = k % n;
        dp[r][c] = 1;
        for (int[] d : DIRS) {
            int x = r + d[0], y = c + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[r][c])
                dp[r][c] = Math.max(dp[r][c], 1 + dp[x][y]);
        }
        best = Math.max(best, dp[r][c]);
    }
    return best;
}

No recursion and polynomial, but the sort adds a log factor.

OptimalDFS + Memoization

Time O(mn)Space O(mn)

Same DFS as brute force, but store the result in memo[r][c] (0 = not computed yet). Each cell is solved once and checks 4 neighbours, so the total work is O(mn). The DFS itself discovers the topological order — no sorting needed.

Java

private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, best = 0;
    int[][] memo = new int[m][n];
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            best = Math.max(best, dfs(matrix, r, c, memo));
    return best;
}
private int dfs(int[][] a, int r, int c, int[][] memo) {
    if (memo[r][c] != 0) return memo[r][c]; // already solved
    int len = 1;
    for (int[] d : DIRS) {
        int x = r + d[0], y = c + d[1];
        if (x >= 0 && x < a.length && y >= 0 && y < a[0].length && a[x][y] > a[r][c])
            len = Math.max(len, 1 + dfs(a, x, y, memo));
    }
    return memo[r][c] = len;
}

Linear in the grid size; recursion depth can reach the path length.

Pro tip

Worried about stack depth (a 200×200 snake is 40,000 deep)? Kahn's BFS peels zero-in-degree cells layer by layer; the layer count is the answer, also O(mn).

At a glance

Level	Approach	Time	Space
Brute Force	Plain DFS from Every Cell	`O(mn·3^L)`	`O(mn)`
Better	Sort Cells by Value + DP	`O(mn log(mn))`	`O(mn)`
Optimal	DFS + Memoization	`O(mn)`	`O(mn)`

Common pitfalls

Using ≥ instead of > — equal neighbours create cycles and infinite recursion.
Caching with memo == 0 as “unknown” is safe only because every answer is ≥ 1.
Starting DFS only from (0,0) or from minima — take the max over all cells.

Interview tips

Say why no visited set is needed: strictly increasing ⇒ acyclic (DAG).
Present memo as “longest path starting at (r,c)” — a pure function of the cell.
Mention Kahn's topological sort as the iterative alternative.

Pattern

DFS + memo on an implicit DAG → longest path in a grid/graph where moves follow a strict order.

My notes saved in this browser