Leetcode - 42. Trapping Rain Water

Hard

Dec 26, 2025

#two-pointers

#math

42. Trapping Rain Water

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
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

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

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Constraints:

Notes

Intuition

Water at any position is bounded by the minimum of the maximum heights on its left and right. The two-pointer technique lets us compute this without precomputing all prefix/suffix maximums.

Implementation

Use left and right pointers at opposite ends, tracking maxL (max height seen from left) and maxR (max height seen from right). Update these maxes on each iteration. If maxL ≤ maxR, we know the left side is the bottleneck—add maxL - height[l] to the answer and move left. Otherwise, the right side is the bottleneck—add maxR - height[r] and move right.

Edge-cases

The algorithm handles flat terrain (no trapping) naturally since max - height will be zero. Empty arrays or single-element arrays trap no water.

Time: O(n) — each element visited once
Space: O(1) — only tracking pointers and two max values

Complexity

Solution

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        maxL, maxR = 0, 0
        l, r = 0, len(height) - 1
        trapped = 0
        
        while l < r:
            maxL, maxR = max(maxL, height[l]), max(maxR, height[r])

            if maxL <= maxR:
                trapped += maxL - height[l]
                l += 1
            else:
                trapped += maxR - height[r]
                r -= 1
        
        return trapped

        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()