Please see github.com/anusha-murali for all of my repositories.
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$).