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.