Trapping Rain Water

This simple LeetCode problem (Problem #42) demonstrates the power of two pointers to reduce runtime.

Problem:

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.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Solution

We use two pointers, namely left and right, which will move towards each other from both ends. We also maintain two auxilliary pointers leftMax and rightMax, which will maintain the largest heights encountered so far from the left end and the right end.

Let us say that the left pointer was incremented by 1. Then, the water gain at this step is equal to (leftMax - height(current)), where current is the current index of the left pointer.

In a similar manner, when the right pointer is decremented by 1, the water gain will be (rightMax - height(current)), where current is the current index of the right pointer.

We will illustrate the idea using Example 2 above.

Input: height = [4,2,0,3,2,5]

Step 1: left = 0, right = 5, leftMax = 4, rightMax = 5.

Step 2: Since leftMax = 4 < rightMax = 5, we increment left from 0 to 1.

Step 3: Since height[1] = 2 < leftMax, we don’t update leftMax. We update water, so water = 0 + (leftMax - height[1]) = 0 + (4 - 2) = 2.

Step 4: Still leftMax = 4 < rightMax = 5, so we increment left from 1 to 2.

Step 5: Since height[2] = 0 < leftMax, we don’t update leftMax. We update water, so water = 2 + (leftMax - height[2]) = 2 + (4 - 0) = 6.

Step 6: Still leftMax = 4 < rightMax = 5, so we increment left from 2 to 3.

Step 7: Since height[3] = 3 < leftMax, we don’t update leftMax. We update water, so water = 6 + (leftMax - height[3]) = 6 + (4 - 3) = 7.

Step 8: Still leftMax = 4 < rightMax = 5, so we increment left from 3 to 4.

Step 9: Since height[4] = 2 < leftMax, we don’t update leftMax. We update water, so water = 7+ (leftMax - height[4]) = 7 + (4 - 2) = 9.

Step 10: Step 8: Still leftMax = 4 < rightMax = 5, so we increment left from 4 to 5.

Step 11: Since height[5] = 5 = leftMax = rightMax, we don’t update either. We update water, so water = 9+ (leftMax - height[5]) = 7 + (5 - 5) = 9.

Since left == right, the while loop terminates at this point, and we return 9.

     def trap(height):
        left = 0
        right = len(height) - 1
        leftMax = height[left]
        rightMax = height[right]
        water = 0

        while left < right:
            if leftMax < rightMax:
                left += 1
                if height[left] > leftMax:
                    leftMax = height[left]
                water += (leftMax - height[left])
            else:
                right -= 1
                if height[right] > rightMax:
                    rightMax = height[right]
                water += (rightMax -height[right])
        return water

Runtime: Runtime is $O(n)$ and the space complexity is $O(n)$ (as we are creating a list of size $n$).

Back to Two Pointers Problems

---

anusha-murali.github.io