Leetcode 42 - Trapping Rain Water

Problem Description

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.

Thought Process / Intuition

This is actually a problem that we first encountered in CS2040S if I remember correctly, which is a module I took in Y1S2 of my university. Althought I can't remember the solution straight away, I remember the key idea to solving this problem.

The way to tackle the problem is to at any index, calculate the amount of water that can be trapped between the bars. And we will realise that the way to do this is to calculate the maximum height of the bars to the left and right of each bar. Then, the amount of water that can be trapped at each bar is the minimum of the maximum height to the left and right minus the height of the bar itself.

Approach

Let's put into action our thought process explained earlier.

1. We'll create two arrays, 'left' and 'right', to keep track of the tallest bars seen from the left and right sides, respectively.
   • How do we populate these arrays? Simple! We'll traverse the height array twice. Once from left to right, updating the 'left' array with the maximum height encountered so far.
   • Then, we'll go from right to left, updating the 'right' array similarly.
2. Next, we'll iterate through the height array and calculate the amount of water that can be trapped at each bar.
   • The amount of water that can be trapped at each bar is the minimum of the maximum height to the left and right minus the height of the bar itself.
   • We'll sum up these values to get the total amount of water trapped.

Done!

Solution

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left_max = [height[0] for _ in range(n)]
        right_max = [height[-1] for _ in range(n)]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        for j in range(n - 2, -1, -1):
            right_max[j] = max(right_max[j + 1], height[j])
        total = 0
        for k in range(n):
            total += min(left_max[k], right_max[k]) - height[k]
        return total

Complexity Analysis

Time complexity: $O(n)$

It runs in O(n) time, where n is the number of elements in the height list. This is because initializing and populating the left and right lists, as well as computing the final result, all take linear time.

Space complexity: $O(n)$

It requires O(n) space as well, since additional space is used to store the left and right lists, each having the same length as the input list height.