#42HardTwo Pointers

Trapping Rain Water

Water at each index = min(maxLeft, maxRight) - height[i].

AmazonGoogleMicrosoftFacebookApple

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.

Examples

Example 1

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

Example 2

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

Constraints

  • n == height.length
  • 1 ≤ n ≤ 2 × 10⁴
  • 0 ≤ height[i] ≤ 10⁵

Solutions

1
Precompute maxLeft and maxRight Arrays
TimeO(n)SpaceO(n)

For each position, water trapped = min(maxLeft[i], maxRight[i]) - height[i]. Precompute both arrays in two passes. O(n) time, O(n) space.

Visual Animation
def trap(height: list[int]) -> int:
    n = len(height)
    max_left = [0] * n
    max_right = [0] * n
    for i in range(1, n):
        max_left[i] = max(max_left[i-1], height[i-1])
    for i in range(n-2, -1, -1):
        max_right[i] = max(max_right[i+1], height[i+1])
    water = 0
    for i in range(n):
        level = min(max_left[i], max_right[i])
        if level > height[i]:
            water += level - height[i]
    return water

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine LearningBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Two Pointers to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems