Iteration
Pooling Rain Water
Given an array height that tells you the height of each square on a 2D mountain, return the total amount of water that pools after a storm.
Example:
Explanation: There are 4 units of water that pool in the above photo.
You can solve this problem by breaking it into 2 simple cases.
The first case is when the right side is very tall:
In this case, you can efficiently compute the water by walking left-to-right. The water will rise to the maximum height you've seen so far maxLeft.
This means the water at each index is max(maxLeft - height[i], 0). The max(..., 0) is just there to keep this amount from going negative, since you can't have negative water at a square.
The second case is if the left side is very tall:
In this case, you can efficiently compute the water by walking right-to-left, and keeping track of the tallest height you've seen so far maxRight. The amount of water at each index is max(maxRight - height[j], 0).
Algorithm
Surprisingly, you can combine these two cases to solve the problem. You're in case 1 if maxLeft < maxRight, and you're in case 2 otherwise. This is because the right side is effectively "very tall" as long as the maximum height you saw to the left is smaller than the maximum height you saw to the right.
To solve this problem, you initialize both cases and step them towards each other. You choose which case to step based on maxLeft < maxRight.
As you go, you update the total amount of water water.
Here's the code:
Time Complexity O(n). We loop over every index in the array.
Space Complexity O(1). We store 3 numbers which is O(3) = O(1).
