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`.
Overview: 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.
Read the full Google Software Engineer interview experience this question came from
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.
Community answers
Answer by weian60333
class Solution {
private int[] dr = {0,0,1,-1};
private int[] dc = {1,-1,0,0};
public int solve(int[][] heights) {
// can start from any position
int m = heights.length;
int n = heights[0].length;
int ans = 0;
for (int r = 0; r < m; r++){
for (int c = 0; c < n; c++){
ans = Math.max(ans, dfs(-1, -1, r, c, heights, new boolean[m][n]));
}
}
return ans;
}
private int dfs(int pr, int pc, int r, int c,
int[][] heights, boolean[][] visited){
int best = 1; // 至少有h[r][c]
// visit current cell
visited[r][c] = true;
int m = heights.length;
int n = heights[0].length;
// 拜訪鄰居
for (int d = 0; d < 4; d++){
int nr = r + dr[d];
int nc = c + dc[d];
if (!isBouneded(nr, nc, m, n) || visited[nr][nc]) continue;
if (!canMove(pr,pc,r,c,nr,nc,heights)) continue;
best = Math.max(best, 1 + dfs(r,c,nr,nc,heights,visited));
}
// backtrack
visited[r][c] = false;
return best;
}
private boolean canMove(int pr, int pc,
int r, int c,
int nr, int nc,
int[][] heights){
// a -> b -> c
// 1. h[b] >= h[c]
// 2. h[b] < h[c] && h[a] >= h[c]
if (pr == -1 || pc == -1){
return heights[r][c] >= heights[nr][nc];
}
int prevVal = heights[pr][pc];
int curVal = heights[r][c];
int nextVal = heights[nr][nc];
return curVal >= nextVal || (prevVal >= nextVal && curVal < nextVal);
}
private boolean isBouneded(int r, int c, int m, int n){
return r >= 0 && r < m && c >= 0 && c < n;
}
}