LeetCode #329 Hard

Longest Increasing Path in a Matrix

Find the maximum length of a four-directional path whose values strictly increase.

matrixdfsmemoization

02

Intuition

Starting a raw DFS from every cell repeats the same suffix paths exponentially. Strictly increasing moves can never form a cycle because values must rise at every step. That turns the matrix into an implicit DAG, and the best path beginning at a cell depends only on larger neighbors. Memoizing that value solves each cell once.

How to spot this pattern

When moves must strictly increase or decrease, the values themselves impose a DAG even if the grid has undirected adjacency. Memoized DFS is a compact way to compute longest paths in that implicit DAG.

03

Approach

1

Define a reusable path length for each cell

Let dfs(row, col) return the longest increasing path that starts at that cell, counting the cell itself. Initialize its answer to one because stopping immediately is always valid.

2

Extend only to strictly larger neighbors

Inspect the four adjacent positions and recurse when the neighbor is in bounds and has a greater value. Take one plus the largest returned suffix length.

3

Memoize every starting cell

Cache DFS results so overlapping searches reuse completed suffixes. Evaluate every cell as a possible beginning and return the maximum cached path length.

04

Solution

▶1class Solution:
▶2    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
▶3        rows = len(matrix)
▶4        cols = len(matrix[0])
▶5 
▶6        @cache
▶7        def dfs(row, col):
▶8            best = 1
▶9            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
▶10                nr = row + dr
▶11                nc = col + dc
▶12                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[row][col]:
▶13                    best = max(best, 1 + dfs(nr, nc))
▶14            return best
▶15 
▶16        return max(dfs(row, col) for row in range(rows) for col in range(cols))

05

Common pitfalls

Allowing equal-valued moves

✗ Wrong

matrix[nr][nc] >= matrix[row][col]

✓ Right

matrix[nr][nc] > matrix[row][col]

The path must be strictly increasing.

Forgetting to count the current cell

✗ Wrong

best = 0

✓ Right

best = 1

A cell with no larger neighbor still forms a length-one path.

Using one global visited set

✗ Wrong

if (row, col) in visited:
    return 0

✓ Right

@cache
def dfs(row, col):

Cells may belong to many candidate paths; their optimal suffix should be reused, not forbidden.

06

Edge cases

A one-cell matrix

The cell alone forms a path of length one.

All values are equal

Strict comparison permits no move, so every cached length is one.

The best path bends multiple times

Four-directional DFS explores turns without imposing row or column order.

07

Complexity

Time

O(rows * cols)

Space

O(rows * cols)

Memoization computes each cell once and checks four neighbors.