Workspace

Problem workspace

3 day streakD

Trapping Rain Water with a Stack

HardStacksAreas & contributions

The challenge

Return the total water trapped between nonnegative unit-width elevation bars.

Heights are nonnegative integers. Fewer than three bars trap no water.

Example

[0,1,0,2,1,0,1,3,2,1,2,1] → 6.

Use the walkthrough below to inspect the input and each state change.

See Trapping Rain Water with a Stack, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.00110223140516372819210111Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 22

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

A popped floor needs both a left wall and the current right wall.

Indices are zero-based. C++ uses C++17 or later.

def solve(heights):
    stack, water = [], 0
    for right, height in enumerate(heights):
        while stack and height > heights[stack[-1]]:
            floor = stack.pop()
            if not stack: break
            left = stack[-1]
            depth = min(heights[left], height) - heights[floor]
            water += depth * (right - left - 1)
        stack.append(right)
    return water

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap