Free lesson · DSA Mastery - Interview Prep, End to End

Longest Increasing Path in a Matrix

Hard10 min readdsadynamic-programming

Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix switches to a memoized DFS on a DAG: in an m × n grid, find the longest path where each step moves to an orthogonally-adjacent cell with a strictly greater value. Because values strictly increase along any path, no cycles are possible - the grid (with directed edges from cell to greater-valued neighbors) is a DAG. The DP defines dp[i][j] = the length of the longest increasing path starting from cell (i, j), with the transition dp[i][j] = 1 + max(dp[neighbor]) over neighbors with greater values. It's most naturally computed via memoized DFS (since the dependency graph is irregular), and demonstrates that grid DPs aren't always row-by-row - sometimes the DAG structure dictates a memoization order discovered on-the-fly. It also reinforces that DP and DFS are deeply connected, with memoization being the bridge. We present the memoized DFS (canonical).

The insight: each cell can be a starting point of an increasing path, and the longest path starting at (i, j) is 1 + max(longest path starting at greater-valued neighbor). Since values strictly increase along any path, there's no risk of revisiting (no cycles), so DFS terminates naturally. Memoizing avoids recomputing the longest path from each cell. The answer is the max over all cells of dp[i][j].

The Problem

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 path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Constraints:

m == matrix.length; n == matrix[i].length; 1 <= m, n <= 200; 0 <= matrix[i][j] <= 2^31 - 1.

Approaches Overview

#	Approach	Time	Space	Verdict
1	Memoized DFS over the implicit DAG	O(m · n)	O(m · n)	Canonical

Define dp[i][j] = length of the longest strictly-increasing path starting at (i, j). DFS from each cell, recursing into the four orthogonally-adjacent neighbors that have a strictly greater value, taking 1 + the max over those recursive results. Memoize dp[i][j] to avoid recomputation. The answer is the max over all cells. Time and space O(m · n) - each cell is visited once and its result cached.

Approach: Memoized DFS - Canonical

The Idea

The grid with directed edges from each cell to its strictly-greater orthogonal neighbors is a DAG (no cycles because values strictly increase along edges). We want the longest path in this DAG. The natural DP is dp[i][j] = longest path starting at (i, j), computed by DFS: explore each neighbor with greater value, recurse to get its longest path, take 1 + max over them. Memoize so each cell is computed once. The global answer is the max over all cells.

Logic Flowchart

graph TD
    A["memo[i][j] = 0 (uncomputed)"] --> B["for each cell (i, j): dp[i][j] = dfs(i, j)"]
    B --> C["dfs(i, j):"]
    C --> D{"memoized?"}
    D -->|Yes| E["return memo[i][j]"]
    D -->|No| F["best = 1 (just this cell)"]
    F --> G["for each neighbor (ni, nj) with matrix[ni][nj] > matrix[i][j]:"]
    G --> H["best = max(best, 1 + dfs(ni, nj))"]
    H --> G
    G --> I["memo[i][j] = best; return best"]
    I --> B
    B --> J["return max over all cells"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Longest Increasing Path: memoized DFS from each cell explores greater-valued neighbors and returns one plus the maximum recursive length, with the answer being the maximum over all cells.

Code

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

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

private static int dfs(int[][] matrix, int i, int j, int[][] memo) {
    if (memo[i][j] != 0) return memo[i][j];
    int best = 1;                                                         // the cell itself
    for (int[] d : DIRS) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < matrix.length && nj >= 0 && nj < matrix[0].length
            && matrix[ni][nj] > matrix[i][j]) {
            best = Math.max(best, 1 + dfs(matrix, ni, nj, memo));
        }
    }
    memo[i][j] = best;
    return best;
}

// Usage:
// longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]) -> 4
// longestIncreasingPath([[3,4,5],[3,2,6],[2,2,1]]) -> 4

This Java code finds the longest increasing path via memoized DFS: each cell's longest path is one plus the max over greater-valued neighbors, cached to avoid recomputation, returning the global max.

Step-by-Step Walkthrough

Tracing longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]):

graph LR
    F0["dfs(2,1) = '1': greater neighbors (2,0)=2 → dfs(2,0); (1,1)=6 → dfs(1,1)"]
    F1["dfs(2,0) = '2': greater (1,0)=6 → dfs(1,0); dfs(1,0) = 6 → (0,0)=9 → dfs(0,0) = 1; so dfs(1,0) = 2; dfs(2,0) = 3"]
    F2["dfs(1,1) = 6 → (0,1)=9 → dfs(0,1) = 1; so dfs(1,1) = 2; better goes via (2,0): 1+3 = 4"]
    F3["max over all cells = 4 → return 4"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traces the DFS from cell two-one with value one: the path one, two, six, nine has length four, matching the answer.

Result: 4.

Complexity

Time: O(m · n) - each cell's dp value is computed once (memoized); the work per cell is O(1) (four neighbor checks). Space: O(m · n) for the memo plus O(m · n) recursion stack in the worst case (a long path).

Complexity Comparison

Approach	Time	Space	Key Idea
Memoized DFS	O(m · n)	O(m · n)	dp[i][j] = 1 + max(dp[greater neighbors]); cache on the way back

The memoized DFS is the canonical solution. It exploits that the grid (with edges to greater-valued neighbors) is a DAG, so DFS terminates and each cell's longest-path-from-here can be computed once and cached. The implicit topological order (computed lazily by the recursion) is what makes this work without an explicit topological sort.

Variations & Follow-ups

Why is this a DAG, and why does that matter?

The key property: along any increasing path, values strictly increase. So no cycles can exist - a cycle would require returning to a cell already visited, but its value would be both greater than itself (along the cycle) and equal to itself (since it's the same cell), a contradiction. So the directed graph of "cell → greater-valued orthogonal neighbor" is acyclic - a DAG. Why does this matter? Because the longest path in a general graph is NP-hard (think Traveling Salesman), but the longest path in a DAG is polynomial - solvable by DP. The DP works precisely because the DAG structure rules out infinite recursion and guarantees that each subproblem (longest path starting at a cell) has a well-defined value. Without the strictly-increasing property, the problem would be exponentially harder. The general lesson: recognizing that a problem's structure is a DAG unlocks DP-based polynomial solutions. Many problems have implicit DAGs - strict orderings, monotone constraints, prerequisite chains. Identifying the DAG structure and computing longest/shortest paths or counts on it is a powerful technique. Longest Increasing Path is the cleanest grid instance; similar ideas apply to longest chain in a poset, longest path in a topologically-sortable graph, and DAG-based DP in general.

Why memoized DFS instead of bottom-up tabulation?

The grid is a DAG, but its topological order is not obvious - it depends on the values, not on row/column indices. A bottom-up DP would require explicitly sorting cells by value (smallest first, since longest path from a small-value cell depends on larger-value cells) before filling. This works but is more involved than memoized DFS, which discovers the order implicitly: each dfs(i, j) call recurses into greater-valued neighbors first, ensuring their dp values are computed before the caller's. The memoization caches each result, so the total work is O(m · n) regardless of the topological order. Memoized DFS is often cleaner than explicit topological sort + bottom-up DP for DAG problems, especially when:

The DAG is implicit in the data (here, the edges depend on values, not on a static structure).
The topological order is irregular.
You only need values from "reachable" cells (DFS naturally explores only relevant cells).

The general lesson: for DP on DAGs with irregular structure, memoized DFS is the natural implementation. It handles arbitrary dependency orders without explicit sorting. Bottom-up DP shines when the order is regular (e.g., row by row); DFS shines when the order is data-dependent or hard to express as nested loops. Longest Increasing Path illustrates the DFS approach cleanly; the same technique handles many irregular DP problems.

How does this connect DP and graph algorithms?

Longest Increasing Path is a clean instance of a deep connection: DP on a DAG is equivalent to shortest/longest path in the DAG. Specifically: the DP states are the DAG's nodes; the transitions are the DAG's edges; the DP value at a node is the best path length/cost ending or starting at that node; the answer aggregates over the DAG. This perspective unifies many DP problems with graph problems:

Climbing Stairs / Fibonacci: number of paths in a chain DAG.
Knapsack: shortest path in an item-capacity DAG.
LIS: longest path in a "i < j and nums[i] < nums[j]" DAG.
Coin Change: shortest path in an amount-by-coin DAG.

When you see a problem as DP on a DAG, you can apply graph techniques (topological sort, BFS/DFS) and vice versa. The bridge is memoization: it turns the DP into a DAG traversal with cached results. The lesson: DP and DAG path-finding are two views of the same computation. Recognizing this gives you flexibility - implement via memoized DFS when the DAG is irregular, via bottom-up DP when the order is structured, or via explicit shortest-path algorithms (Dijkstra, Bellman-Ford) when edge weights are involved. Longest Increasing Path makes this connection visible: the DP is literally "longest path in the value-ordered DAG," computed via DFS.

How does it differ from path-counting grid DPs?

Earlier grid DPs (Unique Paths, Minimum Path Sum) had a regular movement structure: each cell's predecessors were always "above" and "left," giving a row-by-row fill order. Longest Increasing Path's movement is irregular: each cell's predecessors depend on the values of its neighbors, not on fixed offsets. This is why row-by-row fill doesn't work - the predecessor relation isn't tied to grid positions but to value comparisons. The general lesson: grid DPs come in two flavors based on movement structure:

Regular movement (right/down, knight's moves, etc.): predecessors are fixed offsets; bottom-up DP with nested loops works.
Irregular movement (value-dependent, condition-dependent, dynamic): predecessors aren't fixed; memoized DFS is more natural.

Longest Increasing Path is the canonical irregular-movement grid DP. The technique - memoized DFS treating the grid as an implicit DAG - generalizes to many other irregular grid problems (e.g., "longest path with sum constraints," "reachability under conditions"). Distinguishing regular vs. irregular movement and choosing the right implementation style (loop-based or recursion-based) is part of grid-DP fluency.

What about edge cases?

Single cell: Longest path is 1 (just that cell); answer 1.
All equal values: No strictly-increasing transitions possible; every cell's dp is 1; answer 1.
Strictly monotone grid: Long path possible; the DP finds it.
No valid path of length > 1: Every cell's dp is 1; answer 1.

Common Interview Pitfalls

Forgetting to memoize. Naive DFS revisits cells exponentially many times; memoization is essential for O(m · n).
Using >= instead of >. The problem says strictly increasing; >= would allow equal-value transitions, creating cycles and breaking correctness.
Stack overflow on large grids. For 200 × 200 grids with long paths (up to 40,000 cells), recursion depth can be huge. Use iterative DFS or increase stack size if needed.
Misinterpreting dp[i][j]. Here it's "longest path starting from (i, j)" - not "ending at (i, j)." Either definition works (with the transition reversed); be consistent.

Why This Topic Matters

Longest Increasing Path teaches memoized DFS for DP on an implicit DAG: the grid with edges to greater-valued neighbors is acyclic (strictly increasing rules out cycles), so DFS terminates and each cell's longest-path-from-here can be cached. The implementation differs from regular grid DPs (no row-by-row fill) - the irregular movement structure is best handled by recursive DFS with memoization, which discovers the topological order on-the-fly. The deep connection: DP on a DAG = longest/shortest path in the DAG, with memoization being the bridge between recursive and graph perspectives. This pattern recurs in any problem where the predecessor relation is value-dependent or structure-dependent rather than positional.

The next topic, Remove Boxes, is a 3-D interval DP - the dimensionality leaps to 3-D state to capture richer context. Given boxes in a row, each colored with a number, repeatedly remove a contiguous group of same-colored boxes to earn k² points where k is the group size; maximize the total. The naive 2-D interval dp[i][j] doesn't suffice because the optimal play sometimes depends on boxes outside [i, j] that share the color of the left endpoint - those external same-color boxes might be merged later with the group at the left of [i, j]. So the state augments to dp[i][j][k] where k is the count of additional same-color-as-box-i boxes "waiting" to be merged with the box at i. It's a deep interval-DP problem that introduces state augmentation for partition DPs - when the basic 2-D interval state misses crucial context, add a third dimension capturing that context.

Back to DSA Mastery - Interview Prep, End to End