Introduction

"Water collected between towers" usually refers to the classic trapping-rain-water problem. You are given an array of non-negative heights, and the task is to compute how much water remains trapped after rain between the taller bars.

The problem looks geometric, but the core insight is about boundaries. Water above any position depends on the tallest wall to its left and the tallest wall to its right, not just the nearest neighbors.

Understanding the Core Idea

For each index, the water level is limited by the shorter of the two highest boundaries around it. If the current tower is shorter than that boundary, the difference is trapped water.

For a height array such as [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the tower of height 0 between 1 and 2 can hold 1 unit. The lower middle region before the height 3 tower can hold even more because both sides provide higher boundaries.

The direct formula for one index is:

water_at_i = min(max_left, max_right) - height[i]

You only add positive values. If the current tower is already as tall as the limiting boundary, it traps nothing.

A Straightforward Solution

One way to solve the problem is to precompute the tallest value seen from the left and from the right. Then you evaluate each index once.

1def trap_with_arrays(heights):
2    if not heights:
3        return 0
4
5    n = len(heights)
6    left_max = [0] * n
7    right_max = [0] * n
8
9    left_max[0] = heights[0]
10    for i in range(1, n):
11        left_max[i] = max(left_max[i - 1], heights[i])
12
13    right_max[n - 1] = heights[n - 1]
14    for i in range(n - 2, -1, -1):
15        right_max[i] = max(right_max[i + 1], heights[i])
16
17    trapped = 0
18    for i in range(n):
19        trapped += min(left_max[i], right_max[i]) - heights[i]
20
21    return trapped
22
23
24print(trap_with_arrays([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

This version is easy to reason about. It runs in linear time and uses extra arrays for the prefix and suffix maxima.

The More Efficient Two-Pointer Approach

The same result can be computed with constant extra space by moving inward from both ends. At each step, you advance the side with the lower boundary because that side already determines the maximum possible water level there.

1def trap(heights):
2    left = 0
3    right = len(heights) - 1
4    left_max = 0
5    right_max = 0
6    trapped = 0
7
8    while left <= right:
9        if heights[left] <= heights[right]:
10            if heights[left] >= left_max:
11                left_max = heights[left]
12            else:
13                trapped += left_max - heights[left]
14            left += 1
15        else:
16            if heights[right] >= right_max:
17                right_max = heights[right]
18            else:
19                trapped += right_max - heights[right]
20            right -= 1
21
22    return trapped
23
24
25example = [4, 2, 0, 3, 2, 5]
26print(trap(example))

Why does this work? Suppose the left tower is shorter than the right tower. Then the right side is tall enough to guarantee that the current left position is limited by left_max, not by some unknown smaller value on the right. That lets you resolve the left side immediately without scanning the rest of the array.

Complexity and When It Matters

Both correct approaches above run in O(n) time. The difference is space:

• the prefix-suffix approach uses O(n) extra memory,
• the two-pointer approach uses O(1) extra memory.

In interviews, the two-pointer solution is usually the target. In production code, the array-based approach can still be acceptable if readability matters more than a small auxiliary allocation.

Common Pitfalls

• Looking only at adjacent towers. Local neighbors do not determine trapped water; the highest boundaries on both sides do.
• Forgetting that negative water should never be added. Use the boundary rule, not raw subtraction from arbitrary towers.
• Using a nested scan for every index. That works logically but degrades to quadratic time on large inputs.
• Misunderstanding the two-pointer invariant. You can only safely process the side with the smaller current boundary.
• Skipping empty-array handling. A good implementation returns 0 immediately for an empty input.

Summary

• Water trapped at an index depends on the tallest boundary to the left and right.
• The standard formula is based on the smaller of those two boundaries.
• A prefix-suffix solution is clear and runs in linear time.
• A two-pointer solution keeps the same linear time with constant extra space.
• Most incorrect solutions fail because they reason locally instead of using global boundaries.