Longest Strictly Increasing Path in a Grid with Four-Directional Moves

Given an R x C matrix of integers, return the number of cells on the longest path along which the values strictly increase from each cell to the next.

From any cell you may move only to one of its four orthogonal neighbors: up, down, left or right.

Function Signature

def longest_increasing_path(matrix: list[list[int]]) -> int:

Rules

• Each step goes from a cell to an orthogonally adjacent cell whose value is strictly greater. Equal values cannot follow each other on a path.
• Diagonal moves are not allowed.
• Moves never wrap around the grid: a cell in the last column is not adjacent to the cell in the first column of the same row, and a cell in the last row is not adjacent to the cell in the first row of the same column.
• A path may start at any cell. A single cell is a path of length 1, so the answer is always at least 1.
• Because values strictly increase, a path never visits a cell twice.
• Return only the length of the longest path, counted in cells, not the path itself.

Constraints

• 1 <= R <= 200, where R = len(matrix)
• 1 <= C <= 200, where C = len(matrix[i]) for every row i
• 0 <= matrix[i][j] <= 2^31 - 1

Examples

Example 1

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

The path 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 visits every cell using only horizontal and vertical steps.

Example 2

Input:  matrix = [
  [1, 0],
  [0, 2]
]
Output: 2

Paths such as 0 -> 1 or 0 -> 2 have length 2. The sequence 0 -> 1 -> 2 would need a diagonal step from the 1 in the top-left cell to the 2 in the bottom-right cell, which is not allowed.

Example 3

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

The longest path is 1 -> 2 -> 3. Continuing from 3 to 4 would require wrapping from the last column back to the first, which is not allowed.

Longest Strictly Increasing Path in a Grid

Hints

1. Only the up, down, left and right neighbors that lie inside the grid count: an edge cell has fewer neighbors, and nothing wraps around to the opposite side.
2. Since every step must go to a strictly larger value, a path can never revisit a cell, and neighboring equal values never link up.
3. The best path through a cell is closely tied to the best paths of its orthogonal neighbors; with up to 40,000 cells and paths that can pass through all of them, avoid recomputing the same cell's result many times.

Approach

Treat every cell as a node with a directed edge to each in-bounds orthogonal neighbor holding a strictly greater value. Values strictly increase along every edge, so the graph has no cycles and the answer is the number of nodes on its longest path. The reference counts, for each cell, how many strictly smaller orthogonal neighbors it has (its in-degree), seeds a queue with every cell whose in-degree is zero, and processes cells in topological (Kahn) order while tracking length[cell], the number of cells on the longest increasing path that ends at that cell (initially 1). Invariant: when a cell is dequeued, all of its strictly smaller neighbors were dequeued earlier and each already relaxed it, so length[cell] = 1 + max(length of smaller neighbors) is final. The cell then relaxes every strictly greater neighbor with length[cell] + 1 and decrements that neighbor's in-degree, enqueueing it when the count reaches zero. Every cell is enqueued exactly once, and the answer is the largest length seen. Only the four in-bounds orthogonal neighbors are examined, so diagonal steps and wrap-around moves are never taken, and equal neighbors create no edge, so plateaus of duplicates cannot chain. Edge cases: a 1 x 1 grid or an all-equal grid returns 1 because every cell is a path by itself; single rows and single columns are handled by the same bounds checks. The procedure is iterative, so a path through all 40,000 cells needs no recursion depth.

• Time complexity: O(R * C)
• Space complexity: O(R * C)