Compute rainwater accumulation on a height grid
Company: Chalk
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Mountain Rainfall Accumulation
You are given an `m x n` 2D integer grid `elevation`, where `elevation[r][c]` is the terrain height at cell `(r, c)`.
Assume **1 unit** of rain falls on **each cell** (uniformly). Water from a cell flows **downhill** by repeatedly moving to a neighboring cell with **strictly lower** elevation until it reaches a **local minimum** (a cell that has no strictly lower neighbor).
- Neighbors are the 4 orthogonal cells: up, down, left, right (when in bounds).
- From a cell, water moves to the neighbor that represents the **steepest descent**. You may implement this as moving to the neighbor with the **minimum elevation** among all strictly lower neighbors.
- If there are multiple equally-steep choices (ties), you may break ties **arbitrarily**, so multiple different correct outputs may exist.
### Task
Return an `m x n` integer grid `accum` where:
- `accum[r][c]` equals the **total number of rain units** that eventually end at cell `(r, c)` (including the unit that fell on `(r, c)` itself if it is a sink).
- All non-sink cells should have `0` in `accum` (since they do not collect water permanently).
### Example
**Input**
```text
[
[3, 3, 1, -1],
[2, 3, 3, 1],
[0, 1, 3, 3]
]
```
**One valid output**
```text
[
[0, 0, 0, 6],
[0, 0, 0, 0],
[6, 0, 0, 0]
]
```
**Another valid output** (due to tie-breaking)
```text
[
[0, 0, 0, 7],
[0, 0, 0, 0],
[5, 0, 0, 0]
]
```
(There are 12 cells total, so the sum of all values in `accum` should be 12.)
Quick Answer: This question evaluates understanding of grid-based graph traversal, flow simulation to local minima, and the ability to reason about state propagation and accumulation across cells.
## Mountain Rainfall Accumulation\n\nYou are given an `m x n` 2D integer grid `elevation`, where `elevation[r][c]` is the terrain height at cell `(r, c)`.\n\nExactly **1 unit** of rain falls on **each cell**. From any cell, water flows **downhill**: it repeatedly moves to a neighboring cell of **strictly lower** elevation until it reaches a **local minimum** (a sink — a cell with no strictly-lower neighbor).\n\n- Neighbors are the 4 orthogonal cells (up, down, left, right) that are in bounds.\n- Water takes the **steepest descent**: among the strictly-lower neighbors, move to the one with the **minimum elevation**.\n- **Tie-breaking:** the original problem allows ties to be broken arbitrarily, so several outputs can be valid. For this challenge, break ties **deterministically** by the fixed neighbor order **up, down, left, right** (the first such neighbor wins).\n\n### Task\nReturn an `m x n` integer grid `accum` where `accum[r][c]` equals the **total number of rain units** that eventually settle at cell `(r, c)` — including the unit that fell on `(r, c)` itself when it is a sink. Every non-sink cell must be `0`. The sum of all values in `accum` equals `m * n` (every unit of rain settles somewhere).\n\n### Example\n```text\nelevation = [\n [3, 3, 1, -1],\n [2, 3, 3, 1],\n [0, 1, 3, 3]\n]\n\naccum = [\n [0, 0, 0, 6],\n [0, 0, 0, 0],\n [6, 0, 0, 0]\n]\n```\nCell `(0,3) = -1` is the deepest sink and collects 6 units; cell `(2,0) = 0` collects the other 6. The two sinks total 12 = the number of cells.
Constraints
- 1 <= m, n (the grid has at least one cell when non-empty)
- An empty grid (`[]`) returns an empty grid (`[]`).
- -10^9 <= elevation[r][c] <= 10^9
- Elevations may repeat; equal neighbors are NOT 'lower', so flat plateaus and equal-height cells form their own sinks.
- Because water always moves to a strictly-lower cell, the flow graph has no cycles.
- The sum of all entries in the returned grid equals m * n.
Examples
Input: ([[3, 3, 1, -1], [2, 3, 3, 1], [0, 1, 3, 3]],)
Expected Output: [[0, 0, 0, 6], [0, 0, 0, 0], [6, 0, 0, 0]]
Explanation: The 3x4 example grid. Cell (0,3)=-1 is the lowest sink; the upper-right region drains to it, and (2,0)=0 is the other sink collecting the lower-left.
Input: ([[5]],)
Expected Output: [[1]]
Explanation: Single cell is its own sink; the 1 unit that falls on it stays.
Input: ([],)
Expected Output: []
Explanation: Empty grid returns an empty grid.
Input: ([[1, 2, 3], [6, 5, 4], [7, 8, 9]],)
Expected Output: [[9, 0, 0], [0, 0, 0], [0, 0, 0]]
Explanation: A boustrophedon path of strictly increasing values; every cell flows down the decreasing chain into the global minimum at (0,0)=1, collecting all 9 units.
Input: ([[2, 2], [2, 2]],)
Expected Output: [[1, 1], [1, 1]]
Explanation: All elevations equal, so no cell has a strictly-lower neighbor; every cell is its own sink and keeps its own unit.
Input: ([[3, 2, 1, 2, 3]],)
Expected Output: [[0, 0, 5, 0, 0]]
Explanation: A single-row valley: cells drain toward the center minimum at (0,2)=1.
Input: ([[0, 1, 0], [1, 0, 1], [0, 1, 0]],)
Expected Output: [[2, 0, 2], [0, 3, 0], [1, 0, 1]]
Explanation: Checkerboard of 0s and 1s; each 1 flows to an adjacent 0 (up wins on ties), and the 0 cells are local minima.
Hints
- A cell is a sink if and only if none of its 4 in-bounds neighbors has a strictly lower elevation. The 1 unit on a sink stays there.
- For every non-sink cell, precompute its single 'downhill' target: the strictly-lower neighbor with the minimum elevation (break ties up, down, left, right). This turns the grid into a forest whose roots are sinks.
- Follow each cell's downhill pointers until you hit a sink, then add 1 to that sink's count. Memoize the sink reached from each visited cell so the total work is O(m*n).
- Since every move strictly decreases elevation, the pointer chains can never loop — no visited-set is needed to avoid cycles, only memoization for speed.