Skip to content

42. Trapping Rain Water

On LeetCode ->

Problem

Given bar heights of width \(1\), return the total units of rainwater trapped between them.

height = [4, 2, 0, 3, 2, 5] -> 9
          .
. w w w w .
. w w . w .
. . w . . .
. . w . . .

Key trick

Use two pointers: the lower boundary determines the water at that side because the opposite side already provides a sufficient boundary.

Trap

  • Computing water only between local peaks misses nested basins.
  • Subtracting only peak heights instead of every bar overcounts water.
  • Moving the higher side prevents knowing whether enough support exists opposite it.
  • Boundary and plateau handling commonly causes off-by-one errors.

Why is it interesting?

It reduces a global-looking problem to a one-pass, constant-space decision based on the lower boundary.

Python solution

class Solution:
    def trap(self, height: list[int]) -> int:
        l, r = 0, len(height) - 1
        l_max = r_max = 0
        total = 0

        while l < r:
            # The lower side has a guaranteed boundary on the opposite side.
            if height[l] <= height[r]:
                l_max = max(l_max, height[l])
                total += l_max - height[l]
                l += 1
            else:
                r_max = max(r_max, height[r])
                total += r_max - height[r]
                r -= 1

        return total

Time complexity: \(O(n)\).

Space complexity: \(O(1)\).

Comment on my solution

  • Peak detection skips index n - 2 and does not consistently record boundary peaks.
  • The final peak is added to peaks but not to peaks_index, causing lookup failures.
  • peak_1 can be referenced before assignment when no peaks are found.
  • The last-peak condition compares a valid index with len(peaks), so it cannot succeed.
  • The search mixes len(peaks_index) with indexing into peaks.
  • Water must subtract every bar between boundaries, not only detected peaks.
  • Choosing the globally tallest later peak complicates basin handling and can skip required boundaries.
  • The peak-based scans can take \(O(n^2)\), while two pointers solve the problem in \(O(n)\).
# WRONG
# Peaks calculation is wrong among other things
class Solution:
    def trap(self, height: list[int]) -> int:
        # [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
        # [4,2,0,3,2,5] -> 9

        n = len(height)
        peaks = []
        peaks_index = {}

        for i in range(n - 2):
            if height[i] > height[i + 1]:
                peaks_index[i] = len(peaks)
                peaks.append((i, height[i]))
        if n > 2 and height[-1] > height[-2]:
            peaks.append((n - 1, height[n - 1]))

        print(f"peaks: {peaks}")


        total = 0

        if peaks:
            peak_1 = peaks[0]

        while peak_1:
            peak_1_index = peaks_index[peak_1[0]]

            # this is the last peak
            if peak_1_index == len(peaks):
                break

            farthest_peak = None
            for i in range(peak_1_index + 1, len(peaks_index)):
                later_peak_i, later_peak_h  = peaks[i]
                if farthest_peak is None:
                    farthest_peak =  (later_peak_i, later_peak_h)
                else:
                    prev_i, prev_h = farthest_peak
                    if later_peak_h > prev_h:
                        farthest_peak = (later_peak_i, later_peak_h)

            peak_2 = farthest_peak

            # compute water area between peak_1 and peak_2
            min_height = min(peak_1[1], peak_2[1])
            partial = (peak_2[0] - (peak_1[0] + 1)) * min_height
            idx_1 = peaks_index[peak_1[0]]
            idx_2 = peaks_index[peak_2[0]]
            for i in range(idx_1, idx_2 + 1):
                partial -= peaks[i][1]

            total += partial

            peak_1 = peak_2

        return total