Find the Longest Momentum-Aware Water Path
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find the Longest Momentum-Aware Water Path
Given an `m × n` integer height grid, find the maximum number of cells in a valid path.
A path may start at any cell, uses only up/down/left/right moves, and may not visit a cell more than once. Let consecutive path heights be `..., a, b, c`, where `b` is the current cell and `c` is the proposed next cell. The move from `b` to `c` is valid when either:
- `c <= b`, so water moves to an equal or lower height; or
- `c > b` and `a >= c`, so the height from two path positions ago supplies enough momentum.
The first move has no height two positions ago and therefore must go to an equal or lower cell. A one-cell path is valid.
Implement:
```python
def solve(heights: list[list[int]]) -> int:
...
```
## Constraints
- `1 <= m, n <= 4`
- `m * n <= 15`
- `-10^9 <= heights[r][c] <= 10^9`
## Example
```text
heights = [[5, 1, 4]]
result = 3
```
The path `5 -> 1 -> 4` is valid because the last uphill step can use the earlier height `5`.
Quick Answer: Solve a small-grid path problem where water may move to an equal or lower height, while an uphill step depends on the height two positions earlier. Find the longest non-repeating path from any starting cell while handling negative values, equal heights, and momentum-dependent state.
Implement solve(heights). A path may start at any cell, moves up/down/left/right, and may not revisit a cell. If consecutive path heights are ..., a, b, c, the move from b to c is valid when c <= b, or when c > b and a >= c. The first move has no height two positions ago, so it must be to an equal or lower cell. Return the maximum number of cells in a valid path; a one-cell path is valid.
Constraints
- 1 <= rows, columns <= 4
- rows * columns <= 15
- -10^9 <= heights[r][c] <= 10^9
- A path uses four-directional moves and never revisits a cell.
- The first move must be to an equal or lower height.
Examples
Input: ([[1]],)
Expected Output: 1
Explanation: A one-cell path is valid.
Input: ([[1, 1]],)
Expected Output: 2
Explanation: An equal-height first move is allowed.
Hints
- A state needs the visited mask, the current cell, and the preceding cell that supplies possible momentum.
- Memoize the best suffix length for each state; the 15-cell bound makes bitmasks practical.