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.