# The Trapped Pool

> What collects in the valleys after the rain?

Canonical URL: <https://datadriven.io/problems/the_trapped_pool>

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a list of non-negative heights, return the total units of water trapped above the bars after rain. Use the two-pointer approach for O(n).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **trapping rain water** problem, a classic that probes understanding of **prefix/suffix maximums** or the **two-pointer** technique. It is a hard problem that reveals whether a candidate can reason about water levels at each position.

> **Trick to Solving**
>
> Water at each position is determined by the minimum of the tallest bar to its left and the tallest bar to its right, minus the bar's own height. The two-pointer approach computes this in O(1) space.

---

### Break down the requirements

#### Step 1: For each bar, compute the constraining height

The water level above bar i is `min(max_left[i], max_right[i]) - height[i]`, clamped to 0.

#### Step 2: Use two pointers to avoid precomputing arrays

Maintain `left_max` and `right_max` as you move pointers inward. Process the side with the smaller max first, since that side constrains the water level.

---

### The solution

**Two-pointer approach with running max tracking**

```python
def trap_water(heights: list) -> int:
    if len(heights) < 3:
        return 0
    left = 0
    right = len(heights) - 1
    left_max = heights[left]
    right_max = heights[right]
    total = 0
    while left < right:
        if left_max <= right_max:
            left += 1
            if heights[left] > left_max:
                left_max = heights[left]
            else:
                total += left_max - heights[left]
        else:
            right -= 1
            if heights[right] > right_max:
                right_max = heights[right]
            else:
                total += right_max - heights[right]
    return total
```

> **Time and Space Complexity**
>
> **Time:** O(n) for a single pass with two converging pointers.
> 
> **Space:** O(1). Only pointer and max variables are used.

> **Interviewers Watch For**
>
> Explaining WHY you process the side with the smaller max. That side is the bottleneck: no matter how tall bars are on the other side, the water level cannot exceed the smaller max.

> **Common Pitfall**
>
> The brute-force approach of scanning left and right for each bar is O(n^2). The prefix/suffix array approach is O(n) time and O(n) space. The two-pointer approach is optimal at O(n) time and O(1) space.

---

## Common follow-up questions

- How would you solve this with prefix and suffix max arrays? _(Tests the O(n) space alternative that is easier to reason about.)_
- What if the elevation map was 2D (trapping rain water II)? _(Tests BFS with a priority queue on the boundary cells.)_
- How would you handle negative elevations? _(Tests normalizing by shifting all values up by the minimum.)_
- What if the bars had different widths? _(Tests adapting the area calculation to account for variable widths.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_trapped_pool)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.