Search
⌘K
Two Pointers

Trapping Rain Water

hard
DESCRIPTION (inspired by Leetcode.com)

Write a function to calculate the total amount of water trapped between bars on an elevation map, where each bar's width is 1. The input is given as an array of n non-negative integers height representing the height of each bar.

Example:

341225102;21365487109
Count: 10
height = [3, 4, 1, 2, 2, 5, 1, 0, 2]

Output:

10

Explanation

We can use the two-pointer technique to solve this problem in O(n) time and O(1) space.
In order for any index in the array to be able to trap rain water, there must be higher bars on both the left and right side of the index. For example, index 2 in the following array has height 1. It can trap water because there are higher bars to the left and right of it.
341225102;
To calculate the exact amount of water that can be trapped at index 2, we first take the minimum height of the highest bars to the left and right of it, which in this case is 4. We then subtract the height of the bar at index 2, which is 1,
341225102;
So if we knew the height of the highest bars to the left and right of every index, we could iterate through the array and calculate the amount of water that can be trapped at each index.
But we don't need to know the exact height of both the highest bars to the left and right of every index. For example, let's say we know the highest bar to the right of index 7 with height 0 has a height of 2.
341225102;
If we also knew that there exists a higher bar than 2 anywhere to the left of index 7, then we also know that the minimum height of the highest bars to the left and right of index 7 is 2. This means that we have enough information to calculate the amount of water that can be trapped at index 7, which is 2 - 0 = 2.
This is the insight behind how the two-pointer technique can be used to solve this problem. We initialize two pointers left and right at opposite ends of the array. We also keep two variables leftMax and rightMax to keep track of the highest bars each pointer has seen.
Visualization
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;

trapping rain water

0 / 1

We now use the values of leftMax and rightMax to visit every single index in the array exactly once. We start by comparing leftMax and rightMax. In this case, rightMax is smaller than leftMax, so we know that:
  1. The maximum height of the highest bar to the right of right - 1 is rightMax
  2. There exists a higher bar than rightMax somewhere to the left of right
These two facts mean that we have enough information to calculate the amount of water that can be trapped at index right - 1. So first we move the right pointer back by 1:
Visualization
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;leftrightleftMaxrightMax
Count: 0

initialize pointers

0 / 1

There are two possible cases to consider when calculating the amount of water that can be trapped at the current index of right:
  1. The height of the bar at index right is smaller than rightMax
  2. The height of the bar at index right is greater than or equal to rightMax
In our case, the height of the bar at index right is smaller than rightMax, so we know that the amount of water that can be trapped at index right is rightMax - height[right], and we can move to the next iteration, which follows the same logic:
Visualization
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;leftrightleftMaxrightMax
Count: 0

move right pointer

0 / 4

Now, we run into case 2, where height[right] is greater than or equal to rightMax. This means we can't trap any water at this index, so instead we update rightMax to the height of the bar at index right to prepare for the next iteration.
Visualization
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;leftright213leftMaxrightMax
Count: 3

move right pointer

0 / 2

The same logic applies when leftMax is less than rightMax, and this continues until every index has been visited exactly once, for a total time complexity of O(n) and a space complexity of O(1).
Visualization
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;leftright213leftMaxrightMax
Count: 3

update leftMax

0 / 7

Solution

Visualization
Try these examples:
def trappingWater(heights):
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    leftMax, rightMax = heights[left], heights[right]
    count = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            if heights[left] >= leftMax:
                leftMax = heights[left]
            else:
                count += leftMax - heights[left]
        else:
            right -= 1
            if heights[right] >= rightMax:
                rightMax = heights[right]
            else:
                count += rightMax - heights[right]
    
    return count
341225102;

trapping rain water

0 / 16

Mark as read

Next: Fixed Length Sliding Window

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations
Guided Practice
Recent interview questions
Learn More
Reading Progress

On This Page

Explanation

Solution

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.

Trapping Rain Water | Hello Interview