After the Storm

TIP103 Unit 12 Session 1 (Click for link to problem statements)

After the Storm

A cross-section of a city block is described by building heights in height, where each bar has width 1. After a rainstorm, water pools in the dips between taller buildings.

Return the total units of water that can be trapped.

def trap(height):
    pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Arrays, Two Pointers, Prefix Maximums

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: When does water actually get trapped above a bar?

  • A: Water sits on top of a bar only if there is a taller bar somewhere to its left and somewhere to its right. The water level above that bar is min(tallest bar to the left, tallest bar to the right), so the water it holds is that level minus its own height.

• Q: Can the bars at the ends of the block hold water?

  • A: No. The first and last bars have an open side, so any water there drains off the edge of the block.

• Q: What should we return for an empty list or a block where heights only rise or only fall?

  • A: 0. With no dip enclosed by taller bars on both sides, no water can pool.

HAPPY CASE
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: Water collects in the dips between the taller bars: 1 unit above index 2, 1 unit above index 4, 2 units above index 5, 1 unit above index 6, and 1 unit above index 9, for 6 total units.

Input: height = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: The walls of height 4 and 5 bound the whole block, so the water level between them is 4. Indices 1-4 trap 2 + 4 + 1 + 2 = 9 units.

EDGE CASE
Input: height = [3, 2, 1]
Output: 0
Explanation: The heights only decrease, so every dip is open on the right and all water drains away.

Input: height = []
Output: 0
Explanation: With no bars there is nowhere for water to pool.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Array Scanning Problems where each position depends on values on both sides of it, we can consider the following approaches:

• Prefix/Suffix Maximums: Precompute the tallest bar to the left and to the right of every index, then the water above index i is min(left_max[i], right_max[i]) - height[i]. This costs O(N) extra space.
• Two Pointers: Walk inward from both ends, tracking the running maximum on each side. The side with the smaller maximum is the bottleneck, so its water contribution can be settled immediately — this reduces the space to O(1).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
The water level above any bar is capped by the shorter of the two walls surrounding it: min(max height to its left, max height to its right). With two pointers starting at the ends, we always advance the pointer on the side with the smaller running maximum. That smaller maximum is guaranteed to be the true bottleneck for the bar we move onto — the other side's maximum can only be at least as tall — so we can add that bar's trapped water immediately without knowing anything else about the middle of the array.

1) If the list is empty, return 0.
2) Set `left` to the first index and `right` to the last index.
3) Set `left_max = height[left]` and `right_max = height[right]`.
4) While `left < right`:
   a) If `left_max <= right_max`, the left wall is the bottleneck:
      - Advance `left` by 1.
      - Update `left_max = max(left_max, height[left])`.
      - Add `left_max - height[left]` to the total water.
   b) Otherwise, the right wall is the bottleneck:
      - Advance `right` by 1 (toward the left).
      - Update `right_max = max(right_max, height[right])`.
      - Add `right_max - height[right]` to the total water.
5) Return the total water.

⚠️ Common Mistakes

• Using the nearest taller bar instead of the tallest bar on each side — the water level is set by the overall maximum wall, not the closest one.
• Taking the max of the two side walls instead of the min; water always spills over the shorter wall.
• Adding water before updating the running maximum, which can produce negative contributions when the new bar is the tallest seen so far.
• Advancing the pointer on the side with the larger maximum — that side is not the bottleneck, so its water cannot be settled yet.
• Forgetting that an empty list or a strictly increasing/decreasing skyline traps 0 units.

4: I-mplement

Implement the code to solve the algorithm.

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max <= right_max:
            # Left wall is the bottleneck; settle the next bar on the left
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            # Right wall is the bottleneck; settle the next bar on the right
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • left_max starts at 0 and right_max at 1, so the left pointer advances first.
  • Index 2 (height 0) traps min(1, 3) - 0 = 1 unit; index 4 (height 1) traps 1; index 5 (height 0) traps 2; index 6 (height 1) traps 1.
  • Once the left pointer reaches the wall of height 3, left_max exceeds right_max, so the right pointer works inward and index 9 (height 1) traps min(3, 2) - 1 = 1 unit.
  • Running total: 1 + 1 + 2 + 1 + 1 = Output: 6

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

  • left_max = 4 and right_max = 5, so the left pointer advances the whole way; the water level across the middle is 4.
  • Index 1 traps 4 - 2 = 2; index 2 traps 4 - 0 = 4; index 3 traps 4 - 3 = 1; index 4 traps 4 - 2 = 2.
  • Running total: 2 + 4 + 1 + 2 = Output: 9

• Input: height = [3, 2, 1]

  • left_max = 3 always exceeds right_max, so the right pointer advances; each new bar becomes the new right_max and contributes 0.
  • Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of bars in height.

• Time Complexity: O(N) because each pointer moves inward one step per iteration and they meet after at most N steps, doing constant work each time.
• Space Complexity: O(1) because we only track two pointers, two running maximums, and the water total; no auxiliary arrays are needed (the prefix/suffix maximum approach would use O(N) extra space).