Course4all
Join us on telegram
Home/dsa/Stack/Trapping Rain Water

Trapping Rain Water

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionMaximal Rectangle
Next Question →Simplify Path