Trapping Rain Water

The problem

height lists the heights of bars that stand side by side on flat ground, each one unit wide. Rain falls on the whole row. Water collects in the dips: it is held in by taller bars on both sides and rises until it would spill over the lower of them. At the two open ends it runs off. Return the total amount of water that stays, counted in unit squares. An empty list holds no water. Aim for O(n) time and constant extra space.

What to write

function solve(height: number[]): number

Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output
6

Input
height = [4,2,0,3,2,5]

Output
9

Constraints

0–10,000 nonnegative heights, each ≤ 10,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You are asked for O(n) time and constant extra space, with up to 10,000 bars. So you cannot scan left and right from every bar, and you cannot keep a list with one entry per bar. A few running values have to be enough.

2. Hint 2: Ask a smaller question

   Forget the whole row and look at one bar of example 1: the 0 that has a 1 on each side of it. How high does the water stand above it? Which two bars in the row decide that height?

3. Hint 3: Name the pattern

   The water above a bar rises to the lower of two heights: the tallest bar on its left and the tallest on its right. Each bar needs something from both sides, so walk in from both ends, keeping the tallest bar seen on each side, and always handle the side whose bar is lower. This is opposing two pointers. Read the lesson on opposing two pointers.

4. Hint 4: State the invariant

   When you handle the lower side, the bar under the other pointer is at least as tall as every bar seen so far on this side. So this side's tallest bar so far is the true water level here, and the total is exact for every bar already passed.

5. Hint 5: Sketch the pseudocode

   left = first position, right = last position. Both tallest values and total start at 0. While left < right: if the left bar is not taller than the right bar, raise left tallest to it if needed, add left tallest minus the bar to total, add 1 to left. Otherwise do the mirror image on the right. Return total.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Track the highest wall seen from each side. Advance the lower side and add the difference between its running maximum and current height.

The slow way

For each bar, look left for the tallest bar and right for the tallest bar. The water above it reaches the lower of those two. It is correct, but every bar scans the whole row again, which is n × n steps. Saving both tallest values for every position first fixes the time but costs two extra lists.

The insight

You never need both tallest values at once. Walk in from both ends and handle the side whose bar is lower. The bar under the other pointer is then at least as tall as everything seen on this side. So this side's tallest bar so far is the lower wall, and it alone sets the water level.

Step by step

1. Start a pointer at each end and track the tallest bar on each side. The water above a bar depends on the tallest bar on each side of it. So each side carries one running value, the tallest bar its pointer has passed, starting at 0 before any bar is seen.
2. Handle the side whose bar is lower. The bar on the other side is then at least as tall as everything seen on this side, so this side's own tallest bar decides the water level. On a tie the left side goes first.
3. Left side: update its tallest bar, add this bar's water, step inward. The water above the bar reaches the tallest bar seen on the left, counting the bar itself. Counting it first means a bar that is the tallest so far adds zero, never a negative amount.
4. Right side: update its tallest bar, add this bar's water, step inward. The mirror image. Here the left bar is the taller one, so the tallest bar seen on the right is the lower wall and sets the level.
5. The pointers met on the tallest bar, which holds no water. Every other bar was handled exactly once. The bar where the pointers meet is at least as tall as all the others, so no water can stand on top of it.

The same numbered steps are the comments in each solution.

function solve(height) {
  // 1. Start a pointer at each end and track the tallest bar on each side
  // (l and r are the pointers; left and right are each side's tallest bar.)
  let l = 0,
    r = height.length - 1,
    left = 0,
    right = 0,
    total = 0;
  while (l < r) {
    // 2. Handle the side whose bar is lower
    if (height[l] <= height[r]) {
      // 3. Left side: update its tallest bar, add this bar's water, step inward
      left = Math.max(left, height[l]);
      total += left - height[l++];
    } else {
      // 4. Right side: update its tallest bar, add this bar's water, step inward
      right = Math.max(right, height[r]);
      total += right - height[r--];
    }
  }
  // 5. The pointers met on the tallest bar, which holds no water
  return total;
}

function solve(height: number[]): number {
  // 1. Start a pointer at each end and track the tallest bar on each side
  // (l and r are the pointers; left and right are each side's tallest bar.)
  let l = 0,
    r = height.length - 1,
    left = 0,
    right = 0,
    total = 0;
  while (l < r) {
    // 2. Handle the side whose bar is lower
    if (height[l] <= height[r]) {
      // 3. Left side: update its tallest bar, add this bar's water, step inward
      left = Math.max(left, height[l]);
      total += left - height[l++];
    } else {
      // 4. Right side: update its tallest bar, add this bar's water, step inward
      right = Math.max(right, height[r]);
      total += right - height[r--];
    }
  }
  // 5. The pointers met on the tallest bar, which holds no water
  return total;
}

def solve(height):
    # 1. Start a pointer at each end and track the tallest bar on each side
    left, right = 0, len(height) - 1
    left_max = right_max = total = 0
    while left < right:
        # 2. Handle the side whose bar is lower
        if height[left] <= height[right]:
            # 3. Left side: update its tallest bar, add this bar's water, step inward
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            # 4. Right side: update its tallest bar, add this bar's water, step inward
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1
    # 5. The pointers met on the tallest bar, which holds no water
    return total

Example 1, traced

Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output
6

Why it works

The water above a bar stands at the lower of the tallest bars on its two sides. When a bar on the lower side is handled, its own side's tallest bar so far is no taller than the bar under the other pointer, so it is the lower of the two. Each bar is filled to exactly that level, once.

Time and space

Time O(n), extra space O(1). Each round handles one bar and moves one pointer one step, so n bars take fewer than n rounds: O(n) time. The two positions, the two tallest heights and the total are all that is stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Update the side's tallest bar before you add the water. Subtracting the bar from the old value gives a negative amount whenever the bar is taller than that value: example 2 would return 5 instead of 9.
• Handle the lower side, not the taller one. On the taller side nothing promises a wall that high on the far side: the row 3, 2, 1 holds no water, yet that version counts 1.

Pattern

Opposing two pointers. Builds on Product of Array Except Self and Container With Most Water.

Keep going