Longest Strictly Rising Four-Direction Walk in an Integer Grid
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a grid of non-negative integers with `m` rows and `n` columns, return the number of cells on the longest walk whose values strictly increase from each cell to the next.
A walk may start at any cell. From each cell it moves to one of the four orthogonally adjacent cells: up, down, left or right. Diagonal moves are not allowed, and a walk may not leave the grid or wrap around its edges.
### Function Signature
```python
def longest_rising_walk(matrix: list[list[int]]) -> int:
```
### Rules
- Every step must go to a cell whose value is strictly greater than the current cell's value. A step between equal values is not allowed.
- The length of a walk is the number of cells it visits. A single cell is a walk of length 1, so the answer is always at least 1.
- Because values strictly increase along a walk, no cell can be visited twice.
- Return only the maximum length. Several walks may share that length; the returned integer is the same either way.
### Constraints
- `m == len(matrix)` and `n == len(matrix[i])` for every row `i`
- `1 <= m <= 200` and `1 <= n <= 200`
- `0 <= matrix[i][j] <= 2**31 - 1`; every value fits in a 32-bit signed integer
- The answer is at most `m * n`, which is at most 40,000.
### Examples
**Example 1**
```text
Input: matrix = [[3, 1, 2, 5, 4]]
Output: 3
```
The walk 1 → 2 → 5 through columns 1, 2 and 3 visits three cells. Every other walk is shorter; for example, 1 → 3 and 4 → 5 visit two cells each.
**Example 2**
```text
Input: matrix = [[7, 7], [7, 7]]
Output: 1
```
Every neighbor has an equal value, so no step is allowed and every walk is a single cell.
**Example 3**
```text
Input: matrix = [
[5, 1, 8],
[4, 2, 7],
[9, 3, 6]
]
Output: 6
```
Starting at the 1 in row 0, column 1, the walk 1 → 2 → 3 → 6 → 7 → 8 moves down, down, right, up and up, ending at row 0, column 2.
Overview: A grid coding problem: find the length of the longest walk of strictly increasing values in an integer matrix, moving only up, down, left or right. It tests modeling a grid as a graph, handling equal neighboring values correctly, and an efficient search over grids of up to 40,000 cells.
Read the full Visa Software Engineer interview experience this question came from
Given a grid `matrix` of non-negative integers with `m` rows and `n` columns, return the number of cells on the longest walk whose values strictly increase from each cell to the next.
A walk may start at any cell. From each cell it moves to one of the four orthogonally adjacent cells: up, down, left or right. Diagonal moves are not allowed, and a walk may not leave the grid or wrap around its edges.
Implement `longest_rising_walk(matrix)`, which returns this length as an integer.
Rules:
- Every step must go to a cell whose value is strictly greater than the current cell's value. A step between equal values is not allowed.
- The length of a walk is the number of cells it visits. A single cell is a walk of length 1, so the answer is always at least 1.
- Because values strictly increase along a walk, no cell can be visited twice.
- Return only the maximum length. Several walks may share that length; the returned integer is the same either way.
Constraints:
- m == len(matrix) and n == len(matrix[i]) for every row i
- 1 <= m <= 200 and 1 <= n <= 200
- 0 <= matrix[i][j] <= 2**31 - 1; every value fits in a 32-bit signed integer
- The answer is at most m * n, which is at most 40,000.
No value in this problem exceeds 2^31 - 1: grid values fit a 32-bit signed int (int in Java and C++), and the returned length is at most 40,000.
Example 1:
Input: matrix = [[3, 1, 2, 5, 4]]
Output: 3
Explanation: The walk 1 -> 2 -> 5 through columns 1, 2 and 3 visits three cells. Every other walk is shorter; for example, 1 -> 3 and 4 -> 5 visit two cells each.
Example 2:
Input: matrix = [[5, 1, 8], [4, 2, 7], [9, 3, 6]]
Output: 6
Explanation: Starting at the 1 in row 0, column 1, the walk 1 -> 2 -> 3 -> 6 -> 7 -> 8 moves down, down, right, up and up, ending at row 0, column 2.
Constraints
- m == len(matrix) and n == len(matrix[i]) for every row i
- 1 <= m <= 200 and 1 <= n <= 200
- 0 <= matrix[i][j] <= 2**31 - 1; every value fits in a 32-bit signed integer
- The answer is at most m * n, which is at most 40,000.
Examples
Input: ([[0]],)
Expected Output: 1
Explanation: Minimum 1x1 grid: the single cell is a walk of one cell, so cells are counted (1), not steps (0).
Input: ([[3, 1, 2, 5, 4]],)
Expected Output: 3
Explanation: Source example 1, a single row: 1 -> 2 -> 5 visits three cells; every other walk is shorter.
Hints
- A step only ever goes from a smaller value to a strictly larger one, so no walk can revisit a cell or loop back on itself.
- Equal neighbors block a step in both directions, diagonal cells are never adjacent, and cells on opposite edges of the grid are not neighbors.
- The answer can reach m * n = 40,000 cells, so avoid re-exploring the same cell's continuations over and over, and make sure a very long walk cannot exhaust the call stack.