AlgoViz
HomeStack

Trapping Rainwater

Hard

Water above a bar is bounded by the taller walls

Problem

Given bar heights, compute how much rainwater is trapped between them.

In simple words

Water above a bar = the shorter of the tallest walls on its left and right, minus its own height.

The idea

Each position holds min(highest bar to its left, highest bar to its right) minus its own height. Two pointers moving inward from the ends let you know the binding side at each step, so it needs O(1) space instead of two prefix arrays.

The trick

  • Move whichever pointer has the smaller wall — that side is the limiting one.
  • Water is never negative; a bar taller than both maxima traps nothing.
  • O(n) time, O(1) space with two pointers.
0
1
0
2
1
0
1
3
2
1
2
1
0
1
2
3
4
5
6
7
8
9
10
11

Step 1 of 14. Brute force: for each bar, find the tallest wall to its left and right. Values: 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1.

1/14
Brute force
timeO(n²)spaceO(1)

Tallest wall each side.

1// for each bar, tallest wall on left and right2for (let i = 0; i < n; i++) {3  const L = max(h[0..i]), R = max(h[i..n-1]);4  water += Math.min(L, R) - h[i];5}

Input

array
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Memory

i
—
left
—
right
—

Output

water
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output:
6
Explanation:
Dips between tall bars hold 6 units.

Example 2

Input:
height = [4, 2, 0, 3, 2, 5]
Output:
9
Explanation:
The valley traps 9 units of water.

Example 3

Input:
height = [3, 2, 1]
Output:
0
Explanation:
A downhill slope traps nothing.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.