Trapping Rain Water

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

The hard part

• Water at position i is bounded by the MINIMUM of: (tallest bar to its left) and (tallest bar to its right)
• Then subtract the bar’s own height: water[i] = max(0, min(left_max[i], right_max[i]) - height[i])
• The two-pointer approach computes this without extra arrays by maintaining running maxes from both ends

Examples

Input	Output
[0,1,0,2,1,0,1,3,2,1,2,1]	6
[4,2,0,3,2,5]	9

For height = [0,1,0,2,1,0,1,3,2,1,2,1], water is trapped in the following pockets:

i	0	1	2	3	4	5	6	7	8	9	10	11
height	0	1	0	2	1	0	1	3	2	1	2	1
water	0	0	1	0	1	2	1	0	0	1	0	0

Total: 0+0+1+0+1+2+1+0+0+1+0+0 = 6

Constraints

• n == height.length
• 1 <= n <= 2×10^4
• 0 <= height[i] <= 10^5

Real-World Applications

Where this pattern appears

• Urban drainage planning — calculate water accumulation in city grids after storms
• Histogram analysis — find “trapped” values below a running maximum in time-series data
• Image flood fill — determine how water would fill depressions in a heightmap
• Resource pooling — model how resources “pool” when blocked by higher-capacity neighbours

Complexity Comparison

Approach	Time	Space	Best When
Two Pointers	O(n)	O(1)	Optimal — best for interviews
Prefix Max Arrays	O(n)	O(n)	Conceptually clearest
Monotonic Stack	O(n)	O(n)	Process column by column (horizontal thinking)

Approach 1: Prefix Max Arrays

✓ Simple

⏱ Time O(n) Three linear passes 💾 Space O(n) Two extra arrays

Start here — it’s the most intuitive. Build two arrays: left_max[i] is the tallest bar from the left up to i, and right_max[i] is the tallest bar from the right down to i. The water at each position is min(left_max[i], right_max[i]) - height[i] (clamped to 0). This directly encodes the core insight: water height is limited by the shorter of the two surrounding walls.

Step-by-step for [0,1,0,2,1,0,1,3,2,1,2,1]

i	height	left_max	right_max	min(l,r)	water
0	0	0	3	0	0
1	1	1	3	1	0
2	0	1	3	1	1
3	2	2	3	2	0
4	1	2	3	2	1
5	0	2	3	2	2
6	1	2	3	2	1
7	3	3	3	3	0
8	2	3	2	2	0
9	1	3	2	2	1
10	2	3	2	2	0
11	1	3	1	1	0

Total: 6 ✓

Animated walkthrough

Prefix max arrays — building left_max, right_max, then computing water

Use Next or Autoplay to watch the left_max array fill from left to right, then right_max from right to left, then see each water cell computed.

Back Autoplay Next Reset

Step 1 of 5

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function trap(height):
    n = len(height)
    left_max = [0] * n; right_max = [0] * n
    left_max[0] = height[0]
    for i in 1..n-1: left_max[i] = max(left_max[i-1], height[i])
    right_max[n-1] = height[n-1]
    for i in n-2..0: right_max[i] = max(right_max[i+1], height[i])
    total = 0
    for i in 0..n-1: total += max(0, min(left_max[i], right_max[i]) - height[i])
    return total

Solution Code

Python

trapping_rain_water_prefix_max.py

"""
Given n non-negative integers representing an elevation map where the width of each
bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
"""


# Approach: Prefix Max Arrays
# Build left_max[i] = max height from height[0] to height[i].
# Build right_max[i] = max height from height[i] to height[n-1].
# Water at i = max(0, min(left_max[i], right_max[i]) - height[i]).
# The minimum of both maxes is the effective wall height that bounds the water.

# Time Complexity: O(n) — three linear passes
# Space Complexity: O(n) — two extra arrays of size n

from typing import List


def trap(height: List[int]) -> int:
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    water = 0
    for i in range(n):
        water += max(0, min(left_max[i], right_max[i]) - height[i])
    return water


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                      # 9

C++

trapping_rain_water_prefix_max.cpp

#include <iostream>
#include <vector>
#include <algorithm>

// Approach: Prefix Max Arrays
// Build left_max[i] = max height from height[0] to height[i].
// Build right_max[i] = max height from height[i] to height[n-1].
// Water at i = max(0, min(left_max[i], right_max[i]) - height[i]).
// The minimum of both maxes is the effective wall height that bounds the water.
//
// Time Complexity: O(n) — three linear passes
// Space Complexity: O(n) — two extra arrays of size n

int trap(std::vector<int>& height) {
    int n = static_cast<int>(height.size());
    if (n == 0) return 0;

    std::vector<int> leftMax(n), rightMax(n);

    leftMax[0] = height[0];
    for (int i = 1; i < n; i++)
        leftMax[i] = std::max(leftMax[i - 1], height[i]);

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--)
        rightMax[i] = std::max(rightMax[i + 1], height[i]);

    int water = 0;
    for (int i = 0; i < n; i++)
        water += std::max(0, std::min(leftMax[i], rightMax[i]) - height[i]);

    return water;
}

int main() {
    std::vector<int> h1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    std::cout << trap(h1) << std::endl; // 6

    std::vector<int> h2 = {4, 2, 0, 3, 2, 5};
    std::cout << trap(h2) << std::endl; // 9

    return 0;
}

Java

trapping_rain_water_prefix_max.java

// Approach: Prefix Max Arrays
// Build leftMax[i] = max height from height[0] to height[i].
// Build rightMax[i] = max height from height[i] to height[n-1].
// Water at i = max(0, min(leftMax[i], rightMax[i]) - height[i]).
// The minimum of both maxes is the effective wall height that bounds the water.
//
// Time Complexity: O(n) — three linear passes
// Space Complexity: O(n) — two extra arrays of size n

public class Main {
    public static int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++)
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);

        int water = 0;
        for (int i = 0; i < n; i++)
            water += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);

        return water;
    }

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));                    // 9
    }
}

JavaScript

trapping_rain_water_prefix_max.js

// Approach: Prefix Max Arrays
// Build leftMax[i] = max height from height[0] to height[i].
// Build rightMax[i] = max height from height[i] to height[n-1].
// Water at i = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]).
// The minimum of both maxes is the effective wall height that bounds the water.
//
// Time Complexity: O(n) — three linear passes
// Space Complexity: O(n) — two extra arrays of size n

function trap(height) {
    const n = height.length;
    if (n === 0) return 0;

    const leftMax = new Array(n);
    const rightMax = new Array(n);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++)
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--)
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);

    let water = 0;
    for (let i = 0; i < n; i++)
        water += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);

    return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5]));                    // 9

Rust

trapping_rain_water_prefix_max.rs

// Approach: Prefix Max Arrays
// Build left_max[i] = max height from height[0] to height[i].
// Build right_max[i] = max height from height[i] to height[n-1].
// Water at i = max(0, min(left_max[i], right_max[i]) - height[i]).
// The minimum of both maxes is the effective wall height that bounds the water.
//
// Time Complexity: O(n) — three linear passes
// Space Complexity: O(n) — two extra arrays of size n

fn trap(height: &[i32]) -> i32 {
    let n = height.len();
    if n == 0 {
        return 0;
    }

    let mut left_max = vec![0i32; n];
    let mut right_max = vec![0i32; n];

    left_max[0] = height[0];
    for i in 1..n {
        left_max[i] = left_max[i - 1].max(height[i]);
    }

    right_max[n - 1] = height[n - 1];
    for i in (0..n - 1).rev() {
        right_max[i] = right_max[i + 1].max(height[i]);
    }

    (0..n)
        .map(|i| 0i32.max(left_max[i].min(right_max[i]) - height[i]))
        .sum()
}

fn main() {
    println!("{}", trap(&[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
    println!("{}", trap(&[4, 2, 0, 3, 2, 5]));                    // 9
}

Go

trapping_rain_water_prefix_max.go

package main

import "fmt"

// Approach: Prefix Max Arrays
// Build leftMax[i] = max height from height[0] to height[i].
// Build rightMax[i] = max height from height[i] to height[n-1].
// Water at i = max(0, min(leftMax[i], rightMax[i]) - height[i]).
// The minimum of both maxes is the effective wall height that bounds the water.
//
// Time Complexity: O(n) — three linear passes
// Space Complexity: O(n) — two extra arrays of size n

func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }

    leftMax := make([]int, n)
    rightMax := make([]int, n)

    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        if height[i] > leftMax[i-1] {
            leftMax[i] = height[i]
        } else {
            leftMax[i] = leftMax[i-1]
        }
    }

    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        if height[i] > rightMax[i+1] {
            rightMax[i] = height[i]
        } else {
            rightMax[i] = rightMax[i+1]
        }
    }

    water := 0
    for i := 0; i < n; i++ {
        minWall := leftMax[i]
        if rightMax[i] < minWall {
            minWall = rightMax[i]
        }
        if minWall > height[i] {
            water += minWall - height[i]
        }
    }
    return water
}

func main() {
    fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})) // 6
    fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))                    // 9
}

Approach 2: Two Pointers (Recommended)

★ Recommended

⏱ Time O(n) Single pass 💾 Space O(1) Four variables only

The O(1) space optimization over prefix max arrays. Instead of pre-building both arrays, maintain running maxes max_left and max_right as the pointers converge inward.

Why it works: If max_left <= max_right, the water at left is definitely max_left - height[left] — even if right_max is higher, the bottleneck is max_left. We don’t need to know the exact right side. Symmetrically for the right pointer.

Step-by-step for [4,2,0,3,2,5]

step	L	h[L]	R	h[R]	ml	mr	process	running water
1	0	4	5	5	0	0	ml<=mr: ml=max(0,4)=4, water+=0, L++	0
2	1	2	5	5	4	0	ml>mr: mr=max(0,5)=5, water+=0, R—	0
3	1	2	4	2	4	5	ml<=mr: water+=4-2=2, L++	2
4	2	0	4	2	4	5	ml<=mr: water+=4-0=4, L++	6
5	3	3	4	2	4	5	ml<=mr: water+=4-3=1, L++	7
6	4	2	4	2	4	5	ml<=mr: water+=4-2=2, L++	9

L >= R, done. Answer: 9 ✓

Pseudocode

function trap(height):
    left, right = 0, len(height) - 1
    max_left, max_right = 0, 0
    water = 0
    while left < right:
        if max_left <= max_right:
            max_left = max(max_left, height[left])
            water += max_left - height[left]
            left++
        else:
            max_right = max(max_right, height[right])
            water += max_right - height[right]
            right--
    return water

Solution Code

Python

trapping_rain_water_two_pointer.py

"""
Given n non-negative integers representing an elevation map where the width of each
bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
"""


# Approach: Two Pointers
# Use left and right pointers, tracking max_left and max_right seen so far.
# Process whichever side has the smaller max — that side's max is the bottleneck.
# water at current position = max_on_that_side - height[current]
# Update max before adding water, then advance the pointer.

# Time Complexity: O(n) — single pass
# Space Complexity: O(1) — four variables only

from typing import List


def trap(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_left, max_right = 0, 0
    water = 0
    while left < right:
        if max_left <= max_right:
            max_left = max(max_left, height[left])
            water += max_left - height[left]
            left += 1
        else:
            max_right = max(max_right, height[right])
            water += max_right - height[right]
            right -= 1
    return water


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                      # 9

C++

trapping_rain_water_two_pointer.cpp

#include <iostream>
#include <vector>
#include <algorithm>

// Approach: Two Pointers
// Use left and right pointers, tracking max_left and max_right seen so far.
// Process whichever side has the smaller max — that side's max is the bottleneck.
// water at current position = max_on_that_side - height[current]
// Update max before adding water, then advance the pointer.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1) — four variables only

int trap(std::vector<int>& height) {
    int left = 0;
    int right = static_cast<int>(height.size()) - 1;
    int maxLeft = 0, maxRight = 0;
    int water = 0;
    while (left < right) {
        if (maxLeft <= maxRight) {
            maxLeft = std::max(maxLeft, height[left]);
            water += maxLeft - height[left];
            left++;
        } else {
            maxRight = std::max(maxRight, height[right]);
            water += maxRight - height[right];
            right--;
        }
    }
    return water;
}

int main() {
    std::vector<int> h1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    std::cout << trap(h1) << std::endl; // 6

    std::vector<int> h2 = {4, 2, 0, 3, 2, 5};
    std::cout << trap(h2) << std::endl; // 9

    return 0;
}

Java

trapping_rain_water_two_pointer.java

// Approach: Two Pointers
// Use left and right pointers, tracking maxLeft and maxRight seen so far.
// Process whichever side has the smaller max — that side's max is the bottleneck.
// water at current position = max_on_that_side - height[current]
// Update max before adding water, then advance the pointer.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1) — four variables only

public class Main {
    public static int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int maxLeft = 0, maxRight = 0;
        int water = 0;
        while (left < right) {
            if (maxLeft <= maxRight) {
                maxLeft = Math.max(maxLeft, height[left]);
                water += maxLeft - height[left];
                left++;
            } else {
                maxRight = Math.max(maxRight, height[right]);
                water += maxRight - height[right];
                right--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));                    // 9
    }
}

JavaScript

trapping_rain_water_two_pointer.js

// Approach: Two Pointers
// Use left and right pointers, tracking maxLeft and maxRight seen so far.
// Process whichever side has the smaller max — that side's max is the bottleneck.
// water at current position = max_on_that_side - height[current]
// Update max before adding water, then advance the pointer.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1) — four variables only

function trap(height) {
    let left = 0, right = height.length - 1;
    let maxLeft = 0, maxRight = 0;
    let water = 0;
    while (left < right) {
        if (maxLeft <= maxRight) {
            maxLeft = Math.max(maxLeft, height[left]);
            water += maxLeft - height[left];
            left++;
        } else {
            maxRight = Math.max(maxRight, height[right]);
            water += maxRight - height[right];
            right--;
        }
    }
    return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5]));                    // 9

Rust

trapping_rain_water_two_pointer.rs

// Approach: Two Pointers
// Use left and right pointers, tracking max_left and max_right seen so far.
// Process whichever side has the smaller max — that side's max is the bottleneck.
// water at current position = max_on_that_side - height[current]
// Update max before adding water, then advance the pointer.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1) — four variables only

fn trap(height: &[i32]) -> i32 {
    let mut left = 0usize;
    let mut right = height.len().saturating_sub(1);
    let mut max_left = 0i32;
    let mut max_right = 0i32;
    let mut water = 0i32;
    while left < right {
        if max_left <= max_right {
            max_left = max_left.max(height[left]);
            water += max_left - height[left];
            left += 1;
        } else {
            max_right = max_right.max(height[right]);
            water += max_right - height[right];
            right -= 1;
        }
    }
    water
}

fn main() {
    println!("{}", trap(&[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
    println!("{}", trap(&[4, 2, 0, 3, 2, 5]));                    // 9
}

Go

trapping_rain_water_two_pointer.go

package main

import "fmt"

// Approach: Two Pointers
// Use left and right pointers, tracking maxLeft and maxRight seen so far.
// Process whichever side has the smaller max — that side's max is the bottleneck.
// water at current position = max_on_that_side - height[current]
// Update max before adding water, then advance the pointer.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1) — four variables only

func trap(height []int) int {
    left, right := 0, len(height)-1
    maxLeft, maxRight := 0, 0
    water := 0
    for left < right {
        if maxLeft <= maxRight {
            if height[left] > maxLeft {
                maxLeft = height[left]
            }
            water += maxLeft - height[left]
            left++
        } else {
            if height[right] > maxRight {
                maxRight = height[right]
            }
            water += maxRight - height[right]
            right--
        }
    }
    return water
}

func main() {
    fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})) // 6
    fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))                    // 9
}

Approach 3: Monotonic Stack

🎯 Interview Favourite

⏱ Time O(n) Each bar pushed and popped once 💾 Space O(n) Stack stores indices

Think horizontally instead of vertically. The stack maintains indices of bars in decreasing height order. When a taller bar appears, we found a right wall. The popped bar is the bottom of the pool. The new stack top is the left wall. Each iteration fills one horizontal layer of water.

Step-by-step for [0,1,0,2,1,0,1,3,2,1,2,1]

i	h[i]	stack before	action	water added
0	0	[]	push 0	0
1	1	[0]	h[1]>h[0]: pop 0, stack empty → break; push 1	0
2	0	[1]	h[2]<=h[1]: push 2	0
3	2	[1,2]	h[3]>h[2]: pop 2, left=1, w=1, water+=min(1,2)-0=1; h[3]>h[1]: pop 1, empty→break; push 3	1
4	1	[3]	h[4]<=h[3]: push 4	0
5	0	[3,4]	h[5]<=h[4]: push 5	0
6	1	[3,4,5]	h[6]>h[5]: pop 5, left=4, w=0, skip; h[6]<=h[4]: break; push 6	0
7	3	[3,4,6]	h[7]>h[6]: pop 6, left=4, w=2, water+=min(1,3)-1=0; pop 4, left=3, w=3…	3

(Remaining steps accumulate total to 6)

Pseudocode

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

Solution Code

Python

trapping_rain_water_stack.py

"""
Given n non-negative integers representing an elevation map where the width of each
bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
"""


# Approach: Monotonic Stack
# Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
# When height[i] > height[stack.top()], we found a right wall — the pool can be filled.
# Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
# Think horizontally: each pop fills one horizontal layer of trapped water.

# Time Complexity: O(n) — each bar is pushed and popped at most once
# Space Complexity: O(n) — stack stores indices

from typing import List


def trap(height: List[int]) -> int:
    stack: List[int] = []
    water = 0
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], height[i]) - height[bottom]
            water += bounded_height * width
        stack.append(i)
    return water


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                      # 9

C++

trapping_rain_water_stack.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

// Approach: Monotonic Stack
// Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
// When height[i] > height[stack.top()], we found a right wall — the pool can be filled.
// Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
// Think horizontally: each pop fills one horizontal layer of trapped water.
//
// Time Complexity: O(n) — each bar is pushed and popped at most once
// Space Complexity: O(n) — stack stores indices

int trap(std::vector<int>& height) {
    std::stack<int> stk;
    int water = 0;
    for (int i = 0; i < static_cast<int>(height.size()); i++) {
        while (!stk.empty() && height[i] > height[stk.top()]) {
            int bottom = stk.top();
            stk.pop();
            if (stk.empty()) break;
            int left = stk.top();
            int width = i - left - 1;
            int boundedHeight = std::min(height[left], height[i]) - height[bottom];
            water += boundedHeight * width;
        }
        stk.push(i);
    }
    return water;
}

int main() {
    std::vector<int> h1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    std::cout << trap(h1) << std::endl; // 6

    std::vector<int> h2 = {4, 2, 0, 3, 2, 5};
    std::cout << trap(h2) << std::endl; // 9

    return 0;
}

Java

trapping_rain_water_stack.java

// Approach: Monotonic Stack
// Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
// When height[i] > height[stack.peek()], we found a right wall — the pool can be filled.
// Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
// Think horizontally: each pop fills one horizontal layer of trapped water.
//
// Time Complexity: O(n) — each bar is pushed and popped at most once
// Space Complexity: O(n) — stack stores indices

import java.util.Deque;
import java.util.ArrayDeque;

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

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));                    // 9
    }
}

JavaScript

trapping_rain_water_stack.js

// Approach: Monotonic Stack
// Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
// When height[i] > height[stack top], we found a right wall — the pool can be filled.
// Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
// Think horizontally: each pop fills one horizontal layer of trapped water.
//
// Time Complexity: O(n) — each bar is pushed and popped at most once
// Space Complexity: O(n) — stack stores indices

function trap(height) {
    const stack = [];
    let water = 0;
    for (let i = 0; i < height.length; i++) {
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop();
            if (stack.length === 0) break;
            const left = stack[stack.length - 1];
            const width = i - left - 1;
            const boundedHeight = Math.min(height[left], height[i]) - height[bottom];
            water += boundedHeight * width;
        }
        stack.push(i);
    }
    return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5]));                    // 9

Rust

trapping_rain_water_stack.rs

// Approach: Monotonic Stack
// Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
// When height[i] > height[stack.last()], we found a right wall — the pool can be filled.
// Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
// Think horizontally: each pop fills one horizontal layer of trapped water.
//
// Time Complexity: O(n) — each bar is pushed and popped at most once
// Space Complexity: O(n) — stack stores indices

fn trap(height: &[i32]) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut water = 0i32;
    for i in 0..height.len() {
        while let Some(&top) = stack.last() {
            if height[i] <= height[top] {
                break;
            }
            stack.pop();
            if let Some(&left) = stack.last() {
                let width = (i - left - 1) as i32;
                let bounded_height = height[left].min(height[i]) - height[top];
                water += bounded_height * width;
            } else {
                break;
            }
        }
        stack.push(i);
    }
    water
}

fn main() {
    println!("{}", trap(&[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
    println!("{}", trap(&[4, 2, 0, 3, 2, 5]));                    // 9
}

Go

trapping_rain_water_stack.go

package main

import "fmt"

// Approach: Monotonic Stack
// Maintain a stack of indices with decreasing heights (a monotonic decreasing stack).
// When height[i] > height[stack top], we found a right wall — the pool can be filled.
// Pop the bottom index, compute water between the new stack top (left wall) and i (right wall).
// Think horizontally: each pop fills one horizontal layer of trapped water.
//
// Time Complexity: O(n) — each bar is pushed and popped at most once
// Space Complexity: O(n) — stack stores indices

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
            bottom := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                break
            }
            left := stack[len(stack)-1]
            width := i - left - 1
            boundedHeight := height[i]
            if height[left] < boundedHeight {
                boundedHeight = height[left]
            }
            boundedHeight -= height[bottom]
            water += boundedHeight * width
        }
        stack = append(stack, i)
    }
    return water
}

func main() {
    fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})) // 6
    fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))                    // 9
}

Common Mistakes

Watch for these pitfalls

• Water formula: min(left_max, right_max) - height[i], NOT max - height[i] — the minimum is what bounds the water level
• Two-pointer: update max_left/max_right before adding water (not after) — the max must include the current bar
• Stack approach: break if the stack is empty after popping (no left wall means no trapped water)

Related Problems

• Container With Most Water ↗ Medium #11
• Largest Rectangle in Histogram ↗ Hard #84
• Trapping Rain Water II ↗ Hard #407

Interview Tips

How to present this in an interview

• Start with prefix max arrays — it’s the clearest explanation of the core insight
• Then present two pointers as the O(1) space optimization — explain the “bottleneck” reasoning: “if max_left is smaller, it doesn’t matter how tall the right wall is”
• The stack approach impresses but is harder to explain — save it as a bonus if asked for alternatives
• The hardest interview question: “Prove two pointers never misses a position” → each position is processed exactly once from whichever side has the smaller max; we never skip a position, we only skip computing it from the wrong side

← Previous
#41 First Missing Positive Next
#45 Jump Game II →