LeetCode 329: Longest Increasing Path in a Matrix

Problem Restatement

We are given an m x n integer matrix.

Return the length of the longest strictly increasing path in the matrix.

From each cell, we may move in four directions:

up, down, left, right

We may not move diagonally, and we may not move outside the matrix boundary. The path must be strictly increasing, so every next cell must have a larger value than the current cell.

Input and Output

Function shape:

def longestIncreasingPath(matrix: list[list[int]]) -> int:
    ...

Examples

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4

One longest increasing path is:

1 -> 2 -> 6 -> 9

So the length is 4.

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4

One longest increasing path is:

3 -> 4 -> 5 -> 6

The value 6 is adjacent to 5, so this path is valid.

Example 3:

Input: matrix = [[1]]
Output: 1

A single cell is already a path of length 1.

First Thought: DFS From Every Cell

A natural idea is to start a DFS from every cell.

From a cell (r, c), try to move to every neighboring cell with a larger value.

The answer is the maximum path length found from any starting cell.

A plain DFS repeats too much work.

For example, many cells may eventually move into the same high-value cell. Without caching, we would recompute the longest path from that high-value cell many times.

Key Insight

Let:

dfs(r, c)

mean:

the length of the longest increasing path starting at cell (r, c)

If we already know dfs for larger neighboring cells, then:

dfs(r, c) = 1 + max(dfs(next_r, next_c))

over all valid neighbors whose value is greater than matrix[r][c].

If there is no larger neighbor, then:

dfs(r, c) = 1

The important part is memoization.

Once we compute dfs(r, c), we store it. Future calls reuse the stored value.

This turns repeated DFS into dynamic programming on a directed acyclic graph. The graph has no cycle because every move must go to a strictly larger value.

Algorithm

Create a memo table memo with the same shape as matrix.

Each memo[r][c] stores the longest increasing path starting from (r, c).

Then:

1. For every cell (r, c), call dfs(r, c).
2. Inside dfs, return memo[r][c] if it was already computed.
3. Start the best length at 1, meaning the path contains the current cell.
4. Try the four directions.
5. If a neighbor is inside the matrix and has a larger value, recursively compute its path.
6. Store the best result in memo[r][c].
7. Return the maximum value over all cells.

Walkthrough

Use:

matrix = [
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]

Consider the cell with value 1 at position (2, 1).

Its larger neighbors include:

2 at (2, 0)
6 at (1, 1)

From 2, we can move to 6, then to 9.

So one path is:

1 -> 2 -> 6 -> 9

Its length is 4.

When dfs(2, 1) computes this value, it stores it in memo[2][1].

If another path later reaches (2, 1), the algorithm does not recompute everything. It directly returns the cached value.

Correctness

For any cell (r, c), every valid increasing path starting there either contains only that cell, or moves first to one of its four neighboring cells with a larger value.

The algorithm checks exactly those possible first moves.

If it moves to a larger neighbor (nr, nc), then the remaining path must be the longest increasing path starting from (nr, nc) to make the total path as long as possible. That value is exactly dfs(nr, nc).

So the best path from (r, c) is:

1 + the maximum dfs value among larger neighbors

or 1 if no larger neighbor exists.

Because every move goes to a strictly larger number, the recursion cannot follow a cycle. Therefore, the recursive definition is well-founded.

The outer loop tries every cell as a possible starting point. The longest increasing path in the whole matrix must start at some cell, so taking the maximum over all dfs(r, c) values gives the correct answer.

Complexity

The recursion stack can also reach O(mn) in the worst case.

Implementation

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        memo = [[0] * cols for _ in range(rows)]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int) -> int:
            if memo[r][c] != 0:
                return memo[r][c]

            best = 1

            for dr, dc in directions:
                nr = r + dr
                nc = 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

        answer = 0

        for r in range(rows):
            for c in range(cols):
                answer = max(answer, dfs(r, c))

        return answer

Code Explanation

We store the matrix size:

rows = len(matrix)
cols = len(matrix[0])

The memo table starts with zeroes:

memo = [[0] * cols for _ in range(rows)]

A value of 0 means the cell has not been computed yet. This is safe because every real path length is at least 1.

The four allowed moves are:

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

Inside dfs, we first check the cache:

if memo[r][c] != 0:
    return memo[r][c]

Then we start with length 1:

best = 1

This means the path contains the current cell even if we cannot move anywhere.

For each neighbor, we check two conditions:

0 <= nr < rows
0 <= nc < cols
matrix[nr][nc] > matrix[r][c]

The first two keep us inside the matrix.

The last condition enforces strict increase.

If the neighbor is valid, we update:

best = max(best, 1 + dfs(nr, nc))

Finally, store and return the result:

memo[r][c] = best
return best

The answer is the maximum dfs value over all starting cells.

Testing

def run_tests():
    s = Solution()

    assert s.longestIncreasingPath([
        [9, 9, 4],
        [6, 6, 8],
        [2, 1, 1],
    ]) == 4

    assert s.longestIncreasingPath([
        [3, 4, 5],
        [3, 2, 6],
        [2, 2, 1],
    ]) == 4

    assert s.longestIncreasingPath([[1]]) == 1

    assert s.longestIncreasingPath([
        [1, 2, 3],
    ]) == 3

    assert s.longestIncreasingPath([
        [3],
        [2],
        [1],
    ]) == 3

    assert s.longestIncreasingPath([
        [7, 7],
        [7, 7],
    ]) == 1

    print("all tests passed")

run_tests()

Test meaning: