Trapping Rain Water

Published at23 Jul 2026

Stack Hard 0 views

Like0

You are given an array of non-negative integers representing elevation heights. After it rains, water gets trapped between the elevations. Compute the total amount of trapped water.

A monotonic decreasing stack efficiently solves this. Iterate through the heights. When the current height is greater than the height at the top of the stack, pop the top (the valley). The water trapped above this valley is determined by the min of the left wall (new top of stack) and right wall (current height), minus the valley height, multiplied by the distance between the walls.

This approach processes each bar once and calculates trapped water volume whenever a right wall is found for a valley.

The monotonic decreasing stack approach processes each bar exactly once. When a taller bar arrives, it forms a right wall for the valley at the top of the stack. The left wall is the new top of stack after popping the valley. The water trapped above that valley is bounded by the shorter of the two walls minus the valley height, spread across the distance between the walls.

This approach might seem complex at first, but it directly models the physics of water: water collects in valleys, and each valley is bounded by the nearest taller wall on the left and right. The stack efficiently discovers these relationships.

Alternative approaches include two-pointer and prefix/suffix max arrays, both also O(n). The stack approach is the most general and extends naturally to other problems.

Edge cases include flat terrain (no water), single bar (no water), and descending terrain (no water).

The stack approach directly models the physical process of water filling valleys. Each time a taller bar is encountered, it reveals a valley that can hold water between the current bar and the previous taller bar in the stack. The amount of water is computed layer by layer, not column by column.

A helpful mental model: the stack holds indices of bars that could potentially serve as left walls. When a taller bar arrives, it becomes a right wall, and water is collected above the valleys formed by the shorter bars between the walls. The process repeats for each layer of valleys.

Understanding this problem deeply will help with other geometric computation problems using stacks.

Example Input & Output

Example 1

Input

[4,2,0,3,2,5]

Output

Explanation

Water trapped: 2 units at index 2 (between 4 and 3), then more between 3 and 5.

Example 2

Input

[0,1,0,2,1,0,1,3,2,1,2,1]

Output

Explanation

Water trapped in 4 valleys between elevations. Visualize as a mountain profile.

Example 3

Input

[1,0,1]

Output

Explanation

Single unit of water trapped at index 1 between two walls of height 1.

Algorithm Flow

Recommendation Algorithm Flow for Trapping Rain Water

Solution Approach

Create a stack to store indices. Iterate through heights. While the stack is not empty and the current height is greater than the height at the top of the stack, pop the top index as the valley. If the stack is empty after popping, no left wall exists, so no water can be trapped. Otherwise, calculate the distance between the current index and the new top of stack minus 1, and the bounded height as the min of the current height and the height at the new top minus the valley height. Add the product to the total water.

function solution(height) {
  var stack = [];
  var water = 0;
  for (var i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      var valley = stack.pop();
      if (!stack.length) break;
      var left = stack[stack.length - 1];
      var distance = i - left - 1;
      var boundedHeight = Math.min(height[i], height[left]) - height[valley];
      water += distance * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

Time complexity is O(n). Space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int solution(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int valley = stack.pop();
                if (stack.isEmpty()) break;
                int left = stack.peek();
                int distance = i - left - 1;
                int boundedHeight = Math.min(height[i], height[left]) - height[valley];
                water += distance * boundedHeight;
            }
            stack.push(i);
        }
        return water;
    }
}

javascript

function solution(height) {
  var stack = [];
  var water = 0;
  for (var i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      var valley = stack.pop();
      if (!stack.length) break;
      var left = stack[stack.length - 1];
      var distance = i - left - 1;
      var boundedHeight = Math.min(height[i], height[left]) - height[valley];
      water += distance * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

php

<?php
function solution($height) {
    $stack = []; $water = 0;
    for ($i = 0; $i < count($height); $i++) {
        while (!empty($stack) && $height[$i] > $height[end($stack)]) {
            $valley = array_pop($stack);
            if (empty($stack)) break;
            $left = end($stack);
            $distance = $i - $left - 1;
            $bounded = min($height[$i], $height[$left]) - $height[$valley];
            $water += $distance * $bounded;
        }
        array_push($stack, $i);
    }
    return $water;
}

python

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

rust

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

typescript

function solution(height: number[]): number {
    var stack: number[] = [];
    var water = 0;
    for (var i = 0; i < height.length; i++) {
        while (stack.length && height[i] > height[stack[stack.length - 1]]) {
            var valley = stack.pop() as number;
            if (!stack.length) break;
            var left = stack[stack.length - 1] as number;
            var distance = i - left - 1;
            var boundedHeight = Math.min(height[i], height[left]) - height[valley];
            water += distance * boundedHeight;
        }
        stack.push(i);
    }
    return water;
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Trapping Rain Water

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Gallery Stock Order Check

Harbor Cargo Lineup

Warehouse Crate Ordering

Festival Drum Echoes

Valid Parentheses Grouping

Next Greater Element

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.