Trapping Rain Water (Stack Approach)

Given an elevation map (array height[]), compute how much water it can trap after raining. Solve using a monotonic stack.

Example 1

Input: [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6

Example 2

Input: [4,2,0,3,2,5] → Output: 9

Solution Approach

Use a monotonic decreasing stack of indices. When we find a bar taller than the stack top, water can be trapped between the current bar, the popped bar, and the new stack top (left boundary).

Maintain a stack of indices with decreasing heights.
For each bar i: while stack non-empty and height[i] > height[stack.top()]:
Pop mid = stack.pop(). If stack is empty break.
Width = i - stack.top() - 1, bounded height = min(height[i], height[stack.top()]) - height[mid]. Add width * bounded height to water.

Java

import java.util.*;

class Solution {
    public int trap(int[] height) {
        int water = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int mid = stack.pop();
                if (stack.isEmpty()) break;
                int left = stack.peek();
                int w = i - left - 1;
                int h = Math.min(height[i], height[left]) - height[mid];
                water += w * h;
            }
            stack.push(i);
        }
        return water;
    }
}

Time Complexity: O(N)
Space Complexity: O(N)