Rain on Brick Towers

Hardtwo pointersAlso known as Trapping Rain Water

A child builds a row of toy-brick towers on the garden table, each one brick wide, standing right next to each other. The heights, in bricks, are something like [2, 0, 3, 1, 0, 2]. Then it rains.

Water collects in the dips between taller towers and spills off where there is nothing to hold it. Looking at the row from the front, each one-brick square of water counts as one unit. How many units of water does the row hold once the rain stops?

Your task

Write trappedWater(heights). heights[i] is the height of tower i. Every tower is 1 unit wide and there are no gaps between them. Water spills off both ends of the row. Return the total units of water held.

Above tower i, water rises to the lower of two levels: the tallest tower anywhere to its left (including itself) and the tallest tower anywhere to its right (including itself). The water above it is that level minus heights[i].

trappedWater(heights: int[]) → int

Examples

Example 1

Input

heights = [2, 0, 3, 1, 0, 2]

Output

Why

Tower 1 sits between walls of 2 and 3, so water rises to 2: 2 units. Towers 3 and 4 have 3 on the left and 2 on the right, so water rises to 2: 1 unit above tower 3 and 2 above tower 4. Total 2 + 1 + 2 = 5.

Example 2

Input

heights = [4, 1, 1, 0, 3]

Output

Why

The right wall is 3, lower than the left wall of 4, so water rises to 3 between them: 2 + 2 + 3 = 7. Looking only at each tower's direct neighbours would miss most of this water.

Constraints

0 ≤ heights.length ≤ 10,000
0 ≤ heights[i] ≤ 100,000

Start with brute force

For every tower, scan everything to its left for the tallest tower, scan everything to its right for the tallest, and add min(leftTallest, rightTallest) - height.

Each tower triggers two scans of up to n towers, so 10,000 towers cost about 100 million steps. The scans repeat almost the same work for neighbouring towers: the tallest tower to the left of tower 501 is nearly always the one you found for tower 500.

Hints

0 of 4 shown

Hint 1
Pick tower 4 in [2, 0, 3, 1, 0, 2]. Its neighbours are 1 and 2, but the water above it rises to 2. Which towers decide that level?
Hint 2
The level above a tower is min(tallest on the left, tallest on the right). Computing both for every tower with two extra lists already gives an O(n) answer. Can you do it without the lists?
Hint 3
Put a pointer at each end and track leftMax and rightMax seen so far. Suppose leftMax ≤ rightMax. For the left pointer's tower, the right side has a wall at least rightMax tall, so its level is set by leftMax alone.
Hint 4
Each step, work on the side with the lower max. Update that side's max with the current tower, add max - height to the total, and move that pointer inward. Stop when the pointers meet.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The water above a tower depends on the tallest tower on each side, and only the lower of the two matters. Walk inward from both ends, tracking the tallest tower seen from each side. If the left side's tallest is the lower one, then for the tower at left there is certainly a wall at least that tall somewhere on the right, so its water level is leftMax. It is safe to settle that tower and move on, and the same holds for the right side.

Trace [2, 0, 3, 1, 0, 2]:

left = 0 (2), right = 5 (2). leftMax 2, rightMax 2. Settle the left: 2 - 2 = 0. Total 0.
left = 1 (0). leftMax 2 ≤ rightMax 2. Water 2 - 0 = 2. Total 2.
left = 2 (3). leftMax becomes 3, now bigger than 2. Settle the right instead: tower 5 holds 2 - 2 = 0.
right = 4 (0). rightMax 2 < 3. Water 2 - 0 = 2. Total 4.
right = 3 (1). Water 2 - 1 = 1. Total 5. Now right = 2 = left, stop. Tower 2 is the tallest and holds nothing.

Each tower is settled once, from whichever side has the lower wall at that moment.

Reference solution

function trappedWater(heights) {
  let left = 0, right = heights.length - 1;
  let leftMax = 0, rightMax = 0, total = 0;
  while (left < right) {
    leftMax = Math.max(leftMax, heights[left]);
    rightMax = Math.max(rightMax, heights[right]);
    // The lower side's max decides the level on that side.
    if (leftMax <= rightMax) {
      total += leftMax - heights[left];
      left++;
    } else {
      total += rightMax - heights[right];
      right--;
    }
  }
  return total;
}

def trapped_water(heights):
    left, right = 0, len(heights) - 1
    left_max = right_max = total = 0
    while left < right:
        left_max = max(left_max, heights[left])
        right_max = max(right_max, heights[right])
        # The lower side's max decides the level on that side.
        if left_max <= right_max:
            total += left_max - heights[left]
            left += 1
        else:
            total += right_max - heights[right]
            right -= 1
    return total

TimeO(n)Each step settles one tower and moves one pointer inward.

SpaceO(1)Two pointers, two running maximums and the total.

Learn the idea: Two Pointers Prefix Sums Monotonic Stack

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code