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
- 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
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
long long solve(const vector<int>& heights) {
vector<int> stack;
long long water = 0;
for (int right = 0; right < static_cast<int>(heights.size()); ++right) {
while (!stack.empty() && heights[right] > heights[stack.back()]) {
int floor = stack.back(); stack.pop_back();
if (stack.empty()) break;
int left = stack.back();
int depth = min(heights[left], heights[right]) - heights[floor];
water += 1LL * depth * (right - left - 1);
}
stack.push_back(right);
}
return water;
}