Stack - 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.

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

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

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.

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)