Trapping Rain Water: definition
Water collects above lower bars when taller boundaries exist on both sides. Add the water above each position to find the total volume.
Task example: Trapping Rain Water
Given non-negative bar heights, each of width 1, return the total units of trapped rainwater. Preserve the order and do not modify the input.
At each index: water = min(tallest left boundary, tallest right boundary) - current height. Include the current bar in both maxima.
Do not sort the heights. Positions define the valleys. Empty arrays and fewer than three bars return 0.
Brute force: video explanation
height = [3, 0, 2, 0, 4] → 7
Prefer reading? Follow the steps below.
- For every index i, start both maxima at height[i]. Scan all earlier bars for left_max and all later bars for right_max.
- The lower maximum limits the water level. Subtract height[i] and add that amount to water. Including the current bar keeps the contribution non-negative.
- For [3, 0, 2, 0, 4], the contributions are [0, 3, 1, 3, 0]. Return 7. A rising array such as [1, 2, 3] traps 0.
Time complexity · O(n²)
For each of n bars, scan n - 1 other bars. Total work is O(n²).
Space complexity · O(1)
Only indices, two maxima, and the total are stored. No copied array or extra list is needed.
Two pointers: video explanation
height = [3, 0, 2, 0, 4] → 7
Prefer reading? Follow the steps below.
- Start left and right at opposite ends, with left_max = right_max = water = 0. Compare the known maxima, not the current endpoint heights.
- Process the side with the smaller known maximum. Update that maximum first, add maximum minus the current height, then move that pointer inward.
- Continue while left <= right, so the final remaining bar is processed once. For [3, 0, 2, 0, 4], the total becomes 7. Stop after the pointers cross.
Why it works: if the bar is below the smaller maximum, the opposite boundary is already high enough. If it sets a new maximum, it holds zero water. Each position can be settled without rescanning the middle.
Time complexity · O(n)
Each iteration settles one bar and moves one pointer. Every bar is processed once: O(n) time, instead of repeated O(n²) scans.
Space complexity · O(1)
Two pointers, two maxima, and a total use O(1) extra space. The original array is unchanged.