Iteration

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:**

$\notag
\texttt{height = [1,3,2,4,3,1,0,2,1]}\\[4bp]
\texttt{=> returns 4}$

**Explanation:** There are 4 units of water that pool in the above photo.

First Few Test Cases:

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)`

.

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).

Mark as Completed: