← Amazon questions
CodingReported in a candidate post, Jul 2025

Trapping rain water

Filed under Amazon · Also reported at Accolite, Adobe, Brane Enterprises, CarTrade Tech Limited, CarWale, Celigo, Cloud Lending, Dell and 27 more

Free read 1 of 3

Bars have width 1, heights are non-negative integers, and water above a bar equals min(left max, right max) minus its height when positive.

The question

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much rain water it can trap.

Constraints

  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Examples

Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Why
Six units of water collect between the taller bars.
Input
[4,2,0,3,2,5]
Output
9
Why
Water fills the valleys between the bars of height 4 and 5.

Approach

  1. Bars have width 1, heights are non-negative integers, and water above a bar equals min(left max, right max) minus its height when positive.

Solution

O(n) time, O(1) space

Python
class Solution:
    def trap(self, height):
        l, r = 0, len(height) - 1
        lmax = rmax = water = 0
        while l < r:
            if height[l] < height[r]:           # left side is the limiting side
                lmax = max(lmax, height[l])
                water += lmax - height[l]
                l += 1
            else:
                rmax = max(rmax, height[r])
                water += rmax - height[r]
                r -= 1
        return water

Tips

  • What they are testing: Whether you can reduce a per-index formula to a single pass with two pointers.
  • Common mistake: Using the global maximum on both sides or forgetting that water at a bar depends on the smaller of the two side maxima.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.