Trapping Rain Water

Leetcode 42

Picture from Unsplash by Rupert Britton

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.

The idea here is to loop through the height list. Find the tallest bar from the left and the right of the current bar. If they are both taller than the current bar, compare the tallest left bar and the tallest right bar, find the shorter one. Use the shorter one to subtract the height of the current bar will give us how many units of water are trapped. Sounds confusing, right?🧐

Let’s go over the process together:

At index 0, the current height is 0, but there is no bar on the left, no water can be trapped, so we move to the next index.

At index 1, the current height is 1, but there is no bar on the left, no water can be trapped, so we move to the next index.

At index 2, the tallest bar on the left of the current bar is 1, the tallest bar on the right of the current bar is 3. They both are taller than the current bar. The shorter one is the left bar, which has a height of 1. The height of the left tallest bar minus the height of the current bar is one unit of water.

height_of_left_tallest_bar - height_of_current_bar = 1
total_water = 1

We move to the next position.

At index 3, the tallest bar on the left of the current bar is 1, the tallest bar on the right of the current bar is 3. But the left tallest ball is shorter than the current bar, so no water can be trapped here, we move to the next bar.

At index 4, the tallest bar on the left of the current bar is now 2, the tallest bar on the right of the current bar is still 3. They both are taller than the current bar. The shorter one is the left bar, which has a height of 2. The height of the left tallest bar minus the height of the current bar is one unit of water. Now we have 2 units of water.

height_of_left_tallest_bar - height_of_current_bar = 1
total_water = 2

At index 5, the tallest bar on the left of the current bar is 2, the tallest bar on the right of the current bar is 3. They both are taller than the current bar. The shorter one is the left bar, which has a height of 2. The height of the left tallest bar minus the height of the current bar is two units of water. Now we have 4 units of water.

height_of_left_tallest_bar - height_of_current_bar = 2
total_water = 4

At index 6, the tallest bar on the left of the current bar is 2, the tallest bar on the right of the current bar is 3. They both are taller than the current bar. The shorter one is the left bar, which has a height of 2. The height of the left tallest bar minus the height of the current bar is one unit of water. Now we have 5 units of water.

height_of_left_tallest_bar - height_of_current_bar = 1
total_water = 5

At index 7, the tallest bar on the left of the current bar is 2, the tallest bar on the right of the current bar is 2. They both are shorter than the height of the current bar, no water is trapped here.

At index 8, the tallest bar on the left of the current bar is 3, the tallest bar on the right of the current bar is 2. The right tallest right bar is as tall as the current bar, no water is trapped.

At index 9, the tallest bar on the left of the current bar is 3, the tallest bar on the right of the current bar is 2. They both are taller than the current bar. The shorter one is the right bar, which has a height of 2. The height of the right tallest bar minus the height of the current bar is one unit of water. Now we have 6 units of water.

height_of_left_tallest_bar - height_of_current_bar = 1
total_water = 6

At index 10, the tallest bar on the left of the current bar is 3, the tallest bar on the right of the current bar is 1. The right tallest bar is shorter than the height of the current bar, no water is trapped.

At the last index, there is no bar on the right of the current bar, no water is trapped. We have 6 units of water in total.

Hooray, we finally finished it! 😝

See below for the complete final code in python:

class Solution:
    def trap(self, height: List[int]) -> int:
        final = 0
        for i in range(1,len(height)-1):
            # started from 1, ended at len(height-1), no bar is on the left and right of the first and last bar, so we can skip these two.
            left_max = max(height[:i])
            right_max = max(height[i+1:])
            curr_max = min(left_max,right_max)
            water = curr_max - height[i]
            if water>0: final+=water
        return final

The time complexity is O(n²)

The space complexity is O(1)

Hope my explanation is helpful. If you have any questions, feel free to reach out or leave a comment below, I’m always happy to help.🤓