Longest Strictly Increasing Path in a Grid with Four-Directional Moves
Company: New Relic
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given an integer matrix, find the number of cells on the longest path whose values strictly increase, moving only up, down, left, or right with no diagonal steps and no wrap-around at the edges. Tests grid search and the ability to turn a working first solution into an efficient one.
Read the full New Relic Backend Engineer interview experience this question came from
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.
Implement `longest_increasing_path(matrix)`, which returns this length as an integer.
### 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`
No value exceeds 2^31 - 1, so every value fits in a signed 32-bit integer (`int` in Java and C++), and the answer is at most `R * C = 40,000`.
### Example 1
```text
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
```text
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.
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
Input: ([[1, 2, 3], [6, 5, 4], [7, 8, 9]],)
Expected Output: 9
Explanation: Source example 1: the serpentine 1 -> 2 -> ... -> 9 visits all nine cells with orthogonal steps only.
Input: ([[4, 1, 2, 3]],)
Expected Output: 3
Explanation: Source example 3: single row; 1 -> 2 -> 3 is longest because 3 -> 4 would wrap from the last column to the first.
Hints
- 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.
- Since every step must go to a strictly larger value, a path can never revisit a cell, and neighboring equal values never link up.
- 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.