Trapping rain water

Array Two Pointers Dynamic Programming Stack Monotonic Stack

66.8% acceptance

Jan 12, 2026

36124

692

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn trap(height: Vec<i32>) -> i32 {
    if height.len() < 3 {
      return 0;
    }
    
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max_left = 0;
    let mut max_right = 0;
    let mut water = 0;
    
    while left < right {
      if height[left] < height[right] {
        if height[left] >= max_left {
          max_left = height[left];
        } else {
          water += max_left - height[left];
        }
        left += 1;
      } else {
        if height[right] >= max_right {
          max_right = height[right];
        } else {
          water += max_right - height[right];
        }
        right -= 1;
      }
    }
    
    water
  }
}