Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix looks scary — paths can wind anywhere through a grid — but it collapses into a clean DFS + memoization problem once you spot the right subproblem.

The slow way first

The brute force is a plain DFS from every cell: from a cell, recurse into each strictly larger neighbor and take the longest result. Correct, but cells get re-explored over and over — the same sub-path is recomputed from many different starts, which blows up to exponential time on a dense grid.

The question to ask: does the answer for a cell ever change? The longest increasing path that starts at a given cell depends only on that cell and its neighbors — never on how we arrived there. So it is computed once and reused forever. That is the signal for a memo.

The idea: cache the answer per cell

Define dfs(r, c) = the length of the longest strictly increasing path that starts at cell (r, c). It is 1 (the cell alone) plus the best dfs over the strictly larger neighbors. Store each result in a memo dictionary the first time you compute it; every later visit is an O(1) lookup.

Because edges only ever point from a smaller value to a larger one, the recursion can never cycle — a strictly increasing path cannot loop back on itself. No visited-set bookkeeping is needed.

Walk through it

Step through the animation. DFS starts at the 1 and dives up the chain 1 → 2 → 6 → 9. The top cell 9 has no larger neighbor, so it resolves to 1, and the answers cascade back down: memo[6] = 2, memo[2] = 3, memo[1] = 4. Every other cell then reuses those cached values instantly, and the final answer is 4.

Pseudocode

memo = empty map           # (r, c) -> longest path starting at (r, c)
define dfs(r, c):
    if (r, c) in memo: return memo[(r, c)]
    best = 1               # the cell by itself
    for each of the 4 neighbors (nr, nc):
        if in bounds and matrix[nr][nc] > matrix[r][c]:
            best = max(best, 1 + dfs(nr, nc))
    memo[(r, c)] = best
    return best
answer = max(dfs(r, c) over every cell)

The Python solution

def longest_increasing_path(matrix):
    rows, cols = len(matrix), len(matrix[0])
    memo = {}
    def dfs(r, c):
        if (r, c) in memo:
            return memo[(r, c)]
        best = 1
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        memo[(r, c)] = best
        return best
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

• dfs(r, c) returns the longest increasing path that starts at (r, c).
• Lines 5-6 are the memo cache hit — if we already solved this cell, return the stored answer in O(1).
• best = 1 because the path is at least the cell itself.
• The loop tries all four neighbors; we only recurse into a neighbor whose value is strictly larger, which guarantees the path keeps increasing and never cycles.
• Lines 12-13 cache the result before returning, so each cell is fully computed only once.
• The final line tries every cell as a starting point and takes the maximum.

Complexity

The memo holds one entry per cell, and the recursion stack can be as deep as the number of cells in the worst case, so the extra space is O(m·n). Caching turns an exponential search into a linear one.

When this pattern shows up

Practice