Longest Increasing Path In a Matrix

The longest increasing path starting at a cell only depends on the longest increasing paths starting at its strictly-greater neighbors — never on the cell it came from. That “no cycles” property (values only increase) means each cell’s answer can be memoized exactly once, turning an apparently exponential search into a linear scan over the grid.

Brute Force DFS (No Memoization)

Time O(4^(m·n))Space O(m·n)

From every cell, explore every strictly-increasing path via DFS and take the longest one found anywhere in the grid.

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        def dfs(r: int, c: int) -> int:
            best = 1
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            return best
        return max(dfs(r, c) for r in range(m) for c in range(n))

Without caching, the same cell is re-explored from every path that reaches it, and paths overlap heavily — worst case is exponential in the number of cells.

Memoized DFS (Top-Down 2-D DP)

OptimalTime O(m·n)Space O(m·n)

Cache memo[r][c]: the length of the longest increasing path starting at (r, c). Because paths only move to strictly larger values, there is no cycle — once memo[r][c] is computed it never needs to be recomputed, and every cell is visited a bounded number of times overall.

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for _ in range(m)]
        def dfs(r: int, c: int) -> int:
            if memo[r][c]:
                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 < m and 0 <= nc < n 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(m) for c in range(n))

Actual DFS recursion order depends on call order, not a clean sweep, which makes it hard to trace by hand. Since a cell’s memo value only ever depends on strictly greater neighbors, the same table can equivalently be filled by visiting cells in descending order of value — the largest values first (they have no greater neighbor, so memo starts at 1), then smaller values can look up already-computed neighbors. Tracing matrix = [[9,9,4],[6,6,8],[2,1,1]] (the first example) this way:

1 / 10

comparingresult

Grid values: [[9,9,4],[6,6,8],[2,1,1]]. Process cells from largest value to smallest.

Reading the finished table: memo[2][1] = 4 corresponds to the path 1 → 2 → 6 → 9 (up and left through the grid), matching the example’s answer of [1, 2, 6, 9].

Complexity: each cell is computed once, doing O(1) work across its 4 neighbors → O(m·n) time. The memo table plus recursion stack both cost O(m·n) space.