How to Calculate Trapped Rainwater Using Two Pointers and Monotonic Stacks

You can calculate trapped rainwater in O(N) time using either a two-pointer technique with O(1) extra space or a monotonic stack that tracks unbounded bars, both rigorously documented in the labuladong/fucking-algorithm repository.

The "Trapping Rain Water" problem requires computing the total volume of water trapped between bars of varying heights after raining. According to the source code in labuladong/fucking-algorithm, two optimal linear-time approaches exist: a space-efficient two-pointer method and a boundary-tracking monotonic stack method.

Two-Pointer Approach (O(N) Time, O(1) Space)

Core Insight

The water trapped above any bar is limited by the lower of the highest bar to its left and the highest bar to its right. By maintaining two pointers converging from both ends while tracking running maximums (l_max and r_max), you can compute each position's contribution immediately without auxiliary storage.

Algorithm Steps

1. Initialize left = 0, right = height.length - 1, l_max = 0, r_max = 0, and res = 0.
2. While left < right:
   • Update l_max = max(l_max, height[left]) and r_max = max(r_max, height[right]).
   • If l_max < r_max, add l_max - height[left] to res and increment left.
   • Otherwise, add r_max - height[right] to res and decrement right.
3. Return res.

This works because when l_max < r_max, the left side is the bottleneck; the right side is guaranteed to be higher, so water at left is bounded solely by l_max.

Implementation

The Java implementation in 高频面试系列/接雨水.md (lines 182-202) demonstrates this approach:

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int lMax = 0, rMax = 0, res = 0;
        while (left < right) {
            lMax = Math.max(lMax, height[left]);
            rMax = Math.max(rMax, height[right]);
            if (lMax < rMax) {
                res += lMax - height[left];
                left++;
            } else {
                res += rMax - height[right];
                right--;
            }
        }
        return res;
    }
}

Equivalent Python implementation:

def trap(height):
    left, right = 0, len(height) - 1
    l_max = r_max = res = 0
    while left < right:
        l_max = max(l_max, height[left])
        r_max = max(r_max, height[right])
        if l_max < r_max:
            res += l_max - height[left]
            left += 1
        else:
            res += r_max - height[right]
            right -= 1
    return res

Monotonic Stack Approach (O(N) Time, O(N) Space)

Core Insight

A monotonic decreasing stack stores indices of bars that have not yet found a right boundary. When encountering a taller bar, it acts as the right boundary for the popped valley, allowing calculation of trapped water using the width between boundaries and the bounded height.

Algorithm Steps

1. Initialize an empty stack st and result res = 0.
2. Iterate i from 0 to height.length - 1:
   • While st is not empty and height[i] > height[st.peek()]:
     • bottom = st.pop() (the valley index).
     • If st is empty, break (no left boundary exists).
     • left = st.peek() (the left boundary index).
     • Calculate width = i - left - 1.
     • Calculate bounded_height = min(height[i], height[left]) - height[bottom].
     • Add width * bounded_height to res.
   • Push i onto st.
3. Return res.

This technique is cataloged in 数据结构系列/单调栈.md (lines 276-277) as a canonical example of monotonic stack applications.

Implementation

Java implementation using ArrayDeque:

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

Python implementation:

def trap(height):
    stack = []
    res = 0
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded = min(h, height[left]) - height[bottom]
            res += width * bounded
        stack.append(i)
    return res

Method Comparison

• Two-pointer: Consumes O(1) extra space, making it ideal for memory-constrained environments. It processes the array by moving two indices toward the center.
• Monotonic stack: Requires O(N) space for the stack but explicitly identifies which bars form each water pocket's boundaries, useful when you need to know the specific intervals contributing to the total volume.

Summary

• The two-pointer method calculates trapped rainwater by converging from both ends while maintaining running left and right maximums, achieving O(N) time and O(1) space.
• The monotonic stack method uses a decreasing stack to find left and right boundaries for each valley, computing water pockets as taller bars appear.
• Both approaches run in linear time; choose the two-pointer for minimal space usage and the stack when you need boundary index information.
• Reference implementations are available in 高频面试系列/接雨水.md and 数据结构系列/单调栈.md within the labuladong/fucking-algorithm repository.

Frequently Asked Questions

Why does the two-pointer method work without knowing the right max for every element?

When l_max < r_max, the water level at the left pointer is bounded by l_max because the right side is guaranteed to be at least r_max (which is greater than or equal to l_max). Therefore, you can safely calculate the water at left without scanning the entire right portion of the array.

Can the monotonic stack approach be modified to return the specific intervals where water is trapped?

Yes. Instead of just accumulating the result, you can store tuples of (left_index, right_index, water_volume) each time you pop from the stack and calculate a bounded area. This preserves the O(N) time complexity while providing spatial data about each trapped pocket.

Which method should I use in a coding interview?

The two-pointer solution is generally preferred for its optimal space complexity and concise implementation. However, demonstrating the monotonic stack approach shows deeper understanding of data structure patterns, which may be advantageous if the interviewer asks follow-up questions about boundary identification or similar problems like "Largest Rectangle in Histogram."

Does the stack approach handle flat surfaces (equal heights) correctly?

Yes, but you must decide whether to pop equal heights. The standard implementation pops only when height[i] > height[stack.peek()], which keeps equal-height bars in the stack. This treats consecutive equal bars as separate boundaries without affecting the final volume calculation, as the bounded height difference would be zero for the first popped bar of equal height.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}