Trapping Rain Water

Problem in Plain English

Given an array height describing an elevation map where each bar has width 1, compute how many units of rain water are trapped after raining. Water sits above a bar up to the lower of the tallest bars on its left and right.

Problem Statement

Given a non-empty array height of non-negative integers, imagine a row of vertical bars with width 1 and the listed heights. Return the total units of water held between those bars after rain. Water spills past an exposed edge; the bars themselves occupy space and do not count as water.

For each position, the water level is limited by the lower of the tallest bars on its left and right, including the current bar. Subtract the current height from that level and sum the resulting amounts.

Constraints

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

The valleys hold 1 + 1 + 2 + 1 + 1 = 6 units: one above index 2, one above index 4, two above index 5, one above index 6 and one above index 9.

Example 2

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

The trapped amounts per index are 0, 2, 4, 1, 2, 0, which total 9 units of water.

Example 3

Input: height = [2, 0, 2]
Output: 2

The two equal walls bound one zero-height position, which holds 2 units. Equal boundary heights are valid.

Example 4

Input: height = [1, 2, 3, 4]
Output: 0

Every position has no taller wall to its left than its own height, so water drains away.

Example 5

Input: height = [7]
Output: 0

One bar has no interior valley; no water is trapped.

Intuition

A valley holds water only if a wall blocks escape on both sides. The lower wall sets the spill level. In Example 1 at index 5, the tallest wall on the left is 2 and on the right is 3, so height 0 holds min(2, 3) - 0 = 2 units. At a tall peak the bar reaches the water level and holds nothing. Width is 1, so these per-position depths also give volumes.

Approaches

Brute Force Scans

Solution Details

Reveal Brute Force Scans: intuition, complexity, and code

Intuition

For every position, scan the entire prefix and suffix to find its two tallest walls. Apply the spill-level formula directly. This stores only running maxima, but repeatedly scans nearly the same values.

Step-by-Step Logic

Start total at zero. For each index i, reset leftMax and rightMax to zero. Scan indices 0 through i for leftMax and i through the end for rightMax; including i ensures both maxima are at least height[i].
Compute added water as min(leftMax, rightMax) - height[i] and add it to total. At Example 1 index 2, height 0 with maxima 1 and 3 contributes 1.
Repeat for every index, including peaks and edges. Index 4 contributes 1, index 5 contributes 2, index 6 contributes 1, and index 9 contributes 1. All other contributions are zero.
Return total 6. The table lists both scan ranges, their resulting maxima, and each total update.

Why It Works

Any water above the smaller side maximum can escape over that side, so it cannot remain. Water at or below both side maxima is bounded on both sides. Taking their minimum and subtracting the bar height therefore gives exactly the water depth at this position. Including the current bar makes the difference non-negative. Summing all unit-width positions counts the complete volume once.

Dry Run

Brute Force Scans: variable states at each step
i / height	Left scan / maximum	Right scan / maximum	Water level	Added	total before -> after
`0 / 0`	`[0,0] / 0`	`[0,11] / 3`	`0`	`0`	`0 -> 0`
`1 / 1`	`[0,1] / 1`	`[1,11] / 3`	`1`	`0`	`0 -> 0`
`2 / 0`	`[0,2] / 1`	`[2,11] / 3`	`1`	`1`	`0 -> 1`
`3 / 2`	`[0,3] / 2`	`[3,11] / 3`	`2`	`0`	`1 -> 1`
`4 / 1`	`[0,4] / 2`	`[4,11] / 3`	`2`	`1`	`1 -> 2`
`5 / 0`	`[0,5] / 2`	`[5,11] / 3`	`2`	`2`	`2 -> 4`
`6 / 1`	`[0,6] / 2`	`[6,11] / 3`	`2`	`1`	`4 -> 5`
`7 / 3`	`[0,7] / 3`	`[7,11] / 3`	`3`	`0`	`5 -> 5`
`8 / 2`	`[0,8] / 3`	`[8,11] / 2`	`2`	`0`	`5 -> 5`
`9 / 1`	`[0,9] / 3`	`[9,11] / 2`	`2`	`1`	`5 -> 6`
`10 / 2`	`[0,10] / 3`	`[10,11] / 2`	`2`	`0`	`6 -> 6`
`11 / 1`	`[0,11] / 3`	`[11,11] / 1`	`1`	`0`	`6 -> 6`
Finish	all prefixes scanned	all suffixes scanned	none	none	return `6`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the number of bars. At each i, the prefix and suffix scans together inspect n + 1 values, so n positions take O(n^2) time. Only indices, two maxima, and total are stored, giving O(1) extra space. The Python implementation uses loops, not slices that allocate O(n) temporary arrays.

Code

Solution.java

1class Solution {2    public int trap(int[] height) {3        int total = 0;4        for (int i = 0; i < height.length; i++) {5            int leftMax = 0;6            for (int l = 0; l <= i; l++) {7                leftMax = Math.max(leftMax, height[l]);8            }9            int rightMax = 0;10            for (int r = i; r < height.length; r++) {11                rightMax = Math.max(rightMax, height[r]);12            }13            total += Math.min(leftMax, rightMax) - height[i];14        }15        return total;16    }17}

Hints

Hint 1

The water above one bar is decided by the tallest wall to its left and the tallest wall to its right; which one is the bottleneck?

Hint 2

If the tallest wall seen from the left is lower than the tallest from the right, the left one already fixes that bar answer.

Hint 3

Walk in from both ends and always settle the side whose maximum is smaller, since its bottleneck cannot change anymore.

Edge Cases

One or two bars cannot enclose an interior position, so the answer is zero. Empty arrays are outside the public constraints.
Rising, falling, flat, and all-zero arrays hold no water. The absolute wall height alone does not imply a basin.
Equal walls [2, 0, 2] hold 2 units; ties in running maxima must still move one pointer.
Nested basins [4, 2, 0, 3, 2, 5] hold 9 units, including water above the internal bar of height 3.
Maximum length and wall heights can produce 1999800000 units. Keep the total in a type that supports that bound.

Common Mistakes and Interview Tips

Comparing only immediate neighbors misses distant bounding walls. Use maxima over each side.
Updating the total before refreshing a side maximum can add a negative amount when a new peak is reached.
Choosing the larger reached boundary can overestimate water because the smaller opposite wall remains the spill limit.
Multiplying only the width between two walls answers a different geometry question: subtract each intervening bar height and handle all local basins.
Interview tip: derive the lower-wall formula first, then explain why the known opposite boundary is sufficient on the smaller side. Compare quadratic rescanning with linear carried maxima; no prefix/suffix arrays are needed.

Key Takeaway

When each position is bounded by the best values from both sides, converging pointers that track the smaller bound settle every position in one pass.