Measure Water Trapped Between Elevations
Company: Hive.Ai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Measure Water Trapped Between Elevations
Given a list of nonnegative integer elevations where each bar has width one, return the total number of unit cells of water retained after rain.
Implement:
```python
def trapped_water(heights: list[int]) -> int:
...
```
Example: `heights = [0, 3, 0, 2, 0, 4]` returns `7`.
## Constraints and Clarifications
- An empty list and a list with fewer than three bars retain no water.
- Equal-height boundaries are valid.
- Use integer arithmetic.
- The input may be large; target `O(n)` time.
- Discuss the extra-space trade-off between precomputed boundary maxima and a constant-space scan.
## Hints
- Water above a position is limited by the lower of the best boundary on each side.
- If you can prove which side has the smaller guaranteed boundary, you can finalize one position without knowing the entire opposite side.
Quick Answer: Compute how much rainwater is trapped between nonnegative elevation bars in linear time. Explain both prefix-boundary arrays and the constant-space two-pointer proof, including empty inputs, equal boundaries, and large arrays.
Given nonnegative unit-width bar heights, return the total number of unit cells of rain water trapped between the bars. Preserve the input and use a linear-time scan.
Constraints
- The input may be empty and fewer than three bars trap no water.
- Every height is a nonnegative integer.
- The result uses exact integer arithmetic.
- Do not mutate the input.
- Target O(n) time.
Examples
Input: ([],)
Expected Output: 0
Explanation: An empty elevation map traps no water.
Input: ([4],)
Expected Output: 0
Explanation: A single bar cannot form a basin.
Hints
- Water at a position is limited by the smaller boundary maximum.
- When one side has the smaller known boundary, that side can be finalized.
- Move two pointers inward while tracking the best boundary seen from each side.