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. Watch what the memo absorbs: the first time a cell is reached it recurses through its strictly greater neighbors, and every later call returns instantly from the cache. Since a cell’s memo value only ever depends on those strictly greater neighbors, the work stays linear overall. Tracing the real memoized DFS on matrix = [[9,9,4],[6,6,8],[2,1,1]] (the first example):

matrix values

memo[r][c]

dfs calls = 0best memo = —

1 / 10

comparingseenresultcurrent

Start with memo empty (dots). DFS computes each cell as 1 plus the best strictly greater neighbor, then caches it.

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.

Longest Increasing Path In a Matrix

Brute Force DFS (No Memoization)

Memoized DFS (Top-Down 2-D DP)

More 2-D DP practice