Longest Increasing Path in a Matrix

Range Sum Query - Mutable

Minimum Window Substring

Find the maximum path length you can build by moving to orthogonally adjacent cells with strictly larger values.

Given an `m x n` integer matrix, you may start from any cell and move up, down, left, or right. You may only move to a cell with a **strictly larger** value. Return the length of the longest valid path.

**Input / output**
- Input: `matrix: int[][]`
- Output: length of the longest strictly increasing path

**Examples**
1. `matrix = [[9,9,4],[6,6,8],[2,1,1]]` returns `4` from the path `1 -> 2 -> 6 -> 9`.
2. `matrix = [[3,4,5],[3,2,6],[2,2,1]]` returns `4` from the path `3 -> 4 -> 5 -> 6`.
3. `matrix = [[1]]` returns `1`.

**Constraints**
- `1 <= m, n <= 200`
- `-2^31 <= matrix[r][c] <= 2^31 - 1`

**Target complexity**
- Aim for `O(m * n)` or `O(m * n + edges)` time, not exponential search.

**Hints**
1. If you treat each cell as a graph node with directed edges to larger neighbors, the graph is acyclic.
2. Local peaks have outdegree `0`. Repeatedly peel one topological layer at a time, or memoize DFS results per cell.

**Follow-up**
Why does allowing diagonal moves change only the neighbor count, not the core DAG reasoning?

- Draw a directed edge from each cell to any orthogonal neighbor with a larger value.
- Because values must strictly increase along every move, cycles are impossible: you can never come back to an earlier value on the same path.

See the hidden DAG

- Start a DFS from every cell and try every increasing continuation.
- Without caching, many suffix paths are recomputed over and over, so the naive search becomes exponential in the worst case.

Brute-force baseline

- Count each cell's outdegree: how many larger neighbors it can move to. Cells with outdegree `0` are local peaks.
- Put every peak in a queue. Removing one topological layer shortens the longest path by one step from the back.
- When a peak is removed, decrement the outdegree of its smaller neighbors. Any neighbor whose outdegree falls to `0` becomes part of the next layer. The number of layers processed is exactly the longest increasing path length.

Peel topological layers

A topological BFS over the increasing-value DAG avoids recursion depth issues while still achieving optimal complexity.

Final solution (all languages)

- Every valid increasing path ends at some peak. Removing all peaks strips away exactly the last step of every remaining path.
- After one layer is removed, the cells that become new peaks are exactly the cells whose best path length is now one shorter.
- Therefore the number of BFS layers equals the length of the longest increasing path.