# The Water Collector

> Two walls, one sky, and a very important question.

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

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a list of non-negative integers representing wall heights, find two walls (by index) that together with the x-axis form a container holding the maximum amount of water. Water volume between walls at i and j is min(heights[i], heights[j]) * (j - i). Return that maximum volume.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **container with most water** problem (not trapping rain water). It probes the **two-pointer greedy** approach and the ability to reason about why moving the shorter wall inward is always safe.

> **Trick to Solving**
>
> Start with the widest container (left and right at the edges). The volume is `min(h[left], h[right]) * (right - left)`. Moving the taller wall inward can only decrease width without guaranteed height gain. Always move the shorter wall.

---

### Break down the requirements

#### Step 1: Initialize two pointers at the edges

Left starts at 0, right at the last index. This gives the maximum width.

#### Step 2: Compute volume and update the maximum

Volume is `min(heights[left], heights[right]) * (right - left)`.

#### Step 3: Move the shorter wall inward

The shorter wall is the bottleneck. Moving it inward might find a taller wall that increases volume despite decreased width.

---

### The solution

**Two-pointer greedy with shorter wall advancement**

```python
def max_water(heights: list) -> int:
    left = 0
    right = len(heights) - 1
    best = 0
    while left < right:
        width = right - left
        h = min(heights[left], heights[right])
        volume = h * width
        if volume > best:
            best = volume
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best
```

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

> **Interviewers Watch For**
>
> The proof of correctness: moving the shorter wall is safe because any container involving that wall at a narrower width would have smaller volume (same or shorter height, less width).

> **Common Pitfall**
>
> Confusing this with the trapping rain water problem. Container with most water uses two walls to form a container; trapping rain water fills gaps between all walls. Different problems, different solutions.

---

## Common follow-up questions

- Can you prove that the greedy approach finds the global maximum? _(Tests mathematical reasoning about why no skipped pair can be better.)_
- What if walls had different widths? _(Tests modifying the width calculation to sum individual widths.)_
- How would you find the top 3 containers by volume? _(Tests tracking a small heap of best results during the scan.)_
- What is the brute-force complexity? _(Tests that checking all pairs is O(n^2), making the two-pointer approach a significant improvement.)_

## Related

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