Trapping Rain Water — Monotonic Stack Horizontal Layer

Problem 297 · Trapping Rain Water — Stack Approach

Difficulty: Hard · Pattern: Monotonic Stack (horizontal slabs)

Alternative to the two-pointer approach — computes water in horizontal layers.

Intuition

Maintain a monotonic decreasing stack of indices. When a bar is taller than the top of the stack, water is trapped between the current bar and the bar before the top.

Solutions

# Python — stack
def trap(height):
    stack = []; ans = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            mid = stack.pop()
            if stack:
                bounded_height = min(height[stack[-1]], h) - height[mid]
                width = i - stack[-1] - 1
                ans += bounded_height * width
        stack.append(i)
    return ans

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

// C++
int trap(vector<int>& height) {
    stack<int> st; int ans=0;
    for (int i=0;i<(int)height.size();i++) {
        while (!st.empty()&&height[st.top()]<height[i]) {
            int mid=st.top(); st.pop();
            if (!st.empty()) {
                int h=min(height[st.top()],height[i])-height[mid];
                ans+=h*(i-st.top()-1);
            }
        }
        st.push(i);
    }
    return ans;
}

Complexity

Time: O(n)
Space: O(n)

Compare with Two-Pointer

Two-pointer: O(1) space. Stack approach: O(n) but computes horizontal layers which may be more intuitive.