Limited Time Offer:Up to 0% off Hello Interview Premium

⌘K

Tutor

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:

Count: 10

height = [3, 4, 1, 2, 2, 5, 1, 0, 2]

Output:

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.

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,

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.

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

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:

The maximum height of the highest bar to the right of right - 1 is rightMax
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

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:

The height of the bar at index right is smaller than rightMax
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

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

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

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

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

Two Pointers

Trapping Rain Water

DESCRIPTION (inspired by Leetcode.com)

Explanation

Solution

Comments

Questions

Learn

Links

Legal

Contact