Stack • Hard Data Structures

Trapping Rain Water

Calculate how much rain water can be trapped between elevation blocks. While often solved with Two Pointers, the Monotonic Stack solution elegantly calculates horizontal slices of water.

Try Interactive Simulator

Horizontal Slicing

The Two Pointer method calculates water vertically column by column. The Stack method calculates water horizontally, slice by slice, as it identifies bowl shapes.

The Monotonic Rule

We keep a monotonically decreasing stack. As long as bars are going down, no water is trapped. We just push them to the stack, forming the left slope of a bowl.

Closing the Bowl

When we encounter a bar taller than the top of the stack, we found the right wall of a bowl! We pop the bottom, look at the new top (the left wall), and calculate the trapped rectangular slice.

i:0

0

i:1

1

i:2

0

i:3

2

i:4

1

i:5

0

i:6

1

i:7

3

Stack (Stores Indices of Left Slopes)

Empty

Code Tracker

:::

1let stack = []; let ans = 0;

2for (let i = 0; i < height.length; i++) {

3 while (stack.length && height[i] > height[stack[stack.length - 1]]) {

4 let top = stack.pop();

5 if (stack.length === 0) break;

6 let distance = i - stack[stack.length - 1] - 1;

7 let boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];

8 ans += distance * boundedHeight;

9 }

10 stack.push(i);

11}

12return ans;