# 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:

```text
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

| Item | Meaning |
|---|---|
| Input | An integer matrix `matrix` |
| Output | Length of the longest increasing path |
| Movement | Up, down, left, right |
| Not allowed | Diagonal movement or wrap-around |
| Constraint | `1 <= m, n <= 200` |

Function shape:

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

## Examples

Example 1:

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

One longest increasing path is:

```text
1 -> 2 -> 6 -> 9
```

So the length is `4`.

Example 2:

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

One longest increasing path is:

```text
3 -> 4 -> 5 -> 6
```

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

Example 3:

```text
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:

```text
dfs(r, c)
```

mean:

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

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

```text
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:

```text
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:

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

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

Its larger neighbors include:

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

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

So one path is:

```text
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:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | Each cell is computed once, and each computation checks 4 directions |
| Space | `O(mn)` | The memo table stores one value per cell |

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

## Implementation

```python
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:

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

The memo table starts with zeroes:

```python
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:

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

Inside `dfs`, we first check the cache:

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

Then we start with length `1`:

```python
best = 1
```

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

For each neighbor, we check two conditions:

```python
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:

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

Finally, store and return the result:

```python
memo[r][c] = best
return best
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| First sample | Checks branching paths |
| Second sample | Checks no diagonal movement |
| `[[1]]` | Single-cell matrix |
| One row | Horizontal movement |
| One column | Vertical movement |
| All equal values | Strict increase prevents movement |