Course4all

Trapping Rain Water

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Visual Representation

heights = [0, 1, 0, 2] 1. Index 0 (0): Push 0. 2. Index 1 (1): 1 > 0. Pop 0. Stack empty. Push 1. 3. Index 2 (0): 0 < 1. Push 2. 4. Index 3 (2): 2 > 0. Pop 2 (bottom). Top is 1 (left wall). - height = min(2, 1) - 0 = 1 - width = 3 - 1 - 1 = 1 - Water = 1 * 1 = 1
Hard

Examples

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

Level III: Optimal (Monotonic Stack)

Intuition

Use a stack to keep track of indices of bars in decreasing order of height. When we see a bar taller than the top of the stack, it means the bar at the top can trap water. The water level is limited by the current bar and the bar before the stack top (new top).
⏱ O(N)💾 O(N)
java
import java.util.Stack;
public class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0, current = 0;
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int boundedHeight = Math.min(height[current], height[stack.peek()]) - height[top];
                water += distance * boundedHeight;
            }
            stack.push(current++);
        }
        return water;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMaximal Rectangle
Next Question →Simplify Path