# How to Calculate Trapped Rainwater Using Two Pointers and Monotonic Stacks

> Learn to calculate trapped rainwater in O(N) time with two pointers for O(1) space or a monotonic stack in the labuladong algorithm repository. Master this common coding challenge.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**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](https://github.com/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:

```java
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:

```python
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`:

```java
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:

```python
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.