# The Water Gauge

> Elevation bars trap water between peaks - count the volume.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of non-negative integer heights, return the total units of water trapped above the bars after rain using the two-pointer algorithm.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **trapping rain water** problem using prefix/suffix max arrays or two pointers. It probes understanding of how water level at each position is determined by the constraining walls on both sides.

> **Trick to Solving**
>
> Water above bar i equals `min(max_left, max_right) - height[i]`. Precompute left-max and right-max arrays, or use two pointers to avoid extra space.

---

### Break down the requirements

#### Step 1: Compute the maximum height to the left of each position

Build a left-max array where `left_max[i]` is the tallest bar from index 0 to i.

#### Step 2: Compute the maximum height to the right of each position

Build a right-max array where `right_max[i]` is the tallest bar from index i to the end.

#### Step 3: Sum the water at each position

Water at position i is `min(left_max[i], right_max[i]) - height[i]`, clamped to 0.

---

### The solution

**Prefix and suffix max arrays for water level computation**

```python
def trap(heights: list) -> int:
    n = len(heights)
    if n < 3:
        return 0
    left_max = [0] * n
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], heights[i])
    right_max = [0] * n
    right_max[n - 1] = heights[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], heights[i])
    total = 0
    for i in range(n):
        water = min(left_max[i], right_max[i]) - heights[i]
        if water > 0:
            total += water
    return total
```

> **Time and Space Complexity**
>
> **Time:** O(n) for three linear passes.
> 
> **Space:** O(n) for the two max arrays. The two-pointer approach can reduce this to O(1).

> **Interviewers Watch For**
>
> Whether you can explain the two-pointer O(1) space optimization after presenting the array approach. Starting with the clearer array solution and then optimizing shows good problem-solving process.

> **Common Pitfall**
>
> For each position, scanning left and right for the max is O(n) per position, giving O(n^2) total. Precomputing the arrays brings this down to O(n).

---

## Common follow-up questions

- Can you solve this with O(1) extra space? _(Tests the two-pointer approach with running left_max and right_max.)_
- What if the elevation map was 2D? _(Tests BFS from boundaries with a priority queue (Trapping Rain Water II).)_
- What if bars could have negative heights? _(Tests handling the concept of water level relative to the lowest point.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_water_gauge)
- [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.