Leetcode 150 | Day 7: Trapping Rain Water - Naive vs. Optimized

Leetcode 42 | Trapping Rain Water

Approach 1: Naive (Pre-computed Max Arrays)

Leetcode 42 asks us to compute how much rain water was trapped given different topographies. The topographies are represented by an array.

In this writeup we'll use the array example directly from Leetcode.

Example array: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Here is a recreation of the visual provided by Leetcode that corresponds to the example array, height.

This problem is challenging. It took me quite a bit of time to really understand the connection between the visual example and its corresponding array. What exactly is the visual trying to show us? How are the two pieces of information actually connected?

The first breakthrough in understanding exactly what I was looking at came with the realization that the values in the array are the y-values to the bar graph above, and the indexes of the array are the x-values - the positions along the graph. The black bars simply show the height, y, at each of those positions.

Because I think what makes this problem challenging is the lack of initial clarity - I think the most efficient means of writing this up is to begin by demystifying it, using one single index as a concrete anchor before generalizing to a rule.

For no particular reason, I zeroed in on index 2 when I was tracing through this. So, that's where I'll begin here as well.

This is from the same image of the bar graph from above - I have however zoomed in on index 2. Let's take a look at it.

Looking at index 2, we see that we have 1 blue rectangle that has a width of 1, and a height of 1.

Here's what is happening. Each of the grey rectangles represents "land", or an abstract topography. To the left of index 2, at index 1, the land sits at height 1 - the exact same height as the blue water rectangle. To the right of index 2, at index 3, the land rises even higher, to height 2, like a hill. The water at index 2 is sitting in a dip between those two walls.

So what determines how high that water can rise? The walls on either side. Water can only rise as high as the shorter of the two walls holding it in. If it tried to rise any higher, it would simply spill over the shorter side.

Let's test that directly. What would happen if the water at index 2 tried to rise to a y-value of 2 instead of 1?

It overflows over the left wall. Even though the wall on the right (index 3) is tall enough to hold water at height 2, the wall on the left (index 1) is only height 1 - and that's the side that gives out first, subsequently it is the shorter side that decides the outcome, no matter which side it is.

So what we just seen at index 2 generalizes to every index in the array: for any given position, find the tallest wall to its left and the tallest wall to its right. Whichever of those two is shorter sets the true ceiling for the water at that position - the taller wall doesn't matter, because water spills over the shorter one before it could ever reach the taller one. Once we know that ceiling, we subtract the actual ground height at that index, and what's left over is how much water sits there.

That's the entire rule. Every index in the array is analyzed the same: take the smaller of (tallest wall to the left, tallest wall to the right), subtract the ground height at that index from the shortest wall, and that difference is the water trapped there.

Now, why two separate arrays, leftMax and rightMax, instead of just checking the surrounding walls as we go? Because "tallest wall to the left" and "tallest wall to the right" both depend on the entire array on that side, not just the immediate neighbor. Recalculating that from scratch for every single index would mean rescanning large chunks of the array over and over (which I tried, and it resulted in a "Time Limit Exceeded" error). Instead, we scan the array twice - once left to right, once right to left - and store the running 'tallest wall so far' at every index along the way. Then, when it's time to compute the water at any position, both numbers are already sitting there in an array, no rescanning required.

Let's get into the code. Here are the first four lines:

var trap = function(height) {
    const n = height.length;
    const leftMax = new Array(n);
    const rightMax = new Array(n);

1. We start with our function header, which accepts a single parameter - our array height.
2. We create a variable n that is set equal to height.length. This is just a time saver, as n is much faster to type.
3. This solution requires two additional arrays, leftMax and rightMax, the running 'tallest wall so far' values we just talked about. We initialize these arrays and give them a length each of n.

The next line of code is more important than it may appear:

leftMax[0] = height[0];

Since every calculation depends on there being a calculated leftMax value, this line of code serves as the seed, or the initial value, with which we'll compare when we use Math.max slightly later in the code.

Now the for loop:

for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}

The loop is standard, except for 1 small detail - we initialize i to 1, not 0. Why do we do that? Well, remember that just before the for loop we initialized the seed value by setting leftMax[0] = height[0].

For each value in the array, we compare that value to the value directly to the left to determine which value is the max value. That happens in this line of code:

leftMax[i] = Math.max(leftMax[i - 1], height[i]);

Our next step is to make the exact same calculations, but this time from right to left, so that we can determine rightMax. The logic plays out exactly the same, just in reverse order.

rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}

Now that we have max values reading the array height from both left to right and right to left, we have all of the information we need to calculate the amount of trapped water.

Let's bring back that original bar graph so that we can have a visual reference to go along with the following table.

Now let's walk through the following table. We are going to be reading from all three arrays to calculate the trapped water.

Here we go.

Let's return to index 2 - the same index we started with.

At index 2:

• leftMax[2] = 1
• rightMax[2] = 3

We calculate the min of these two values. Why the min? If we refer back to the overflow image from earlier, we can see immediately why.

The wall that sets the min in this example is located at index 1, and its height is 1. That's the value that bounds index 2. The wall that sets the max, at index 7, is height 3 - but that number doesn't matter here, because if the water tried to exceed the min, it would simply overflow. Remember, we want to calculate the water that's trapped.

Referring back to the table above, after we determine whether leftMax or rightMax is the min for each index position, two things that may seem obvious but are worth pointing out are:

1. leftMax and rightMax are always going to be relative to the index position you are currently at, so it's left and right with respect to i.
2. After we determine the min, we also need to determine what the pre-existing height already is at i. For example:
   • If we are looking at index 4, we can see that:
     • leftMax = 2 (from index 3), and
     • rightMax = 3 (from index 7)
   • However, we already have a height value at index 4, so while the min is 2, we can't add 2 units of trapped water to index 4 - we'd encounter the same overflow consequence as earlier.
   • Instead, we subtract the value already at index 4 (which is 1) from the min (which is 2), and thus we have 1 unit of trapped water at index 4.

We need to make sure we update our accumulator variable total each time we find trapped water, and return it as a final step.

Here's the entire solution put together, in case you want to see it all in one place:

var trap = function(height) {
    const n = height.length;
    const leftMax = new Array(n);
    const rightMax = new Array(n);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    let total = 0;
    for (let i = 0; i < n; i++) {
        total += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    return total;
};

This approach has a time complexity and space complexity of O(n). We'll see in the optimized approach that we're able to do better on space complexity, but because our objective is to calculate how much water is trapped, this forces us to examine every position at least once, which necessitates a loop of some form. And that loop means a time complexity of at least O(n).

Approach 2: Optimized (Two Pointer)

This approach uses two pointers, right and left. Conceptually it's quite similar to the naive approach, except one very critical detail, because we are using two pointers (one starting at each end of the array), we save memory by not having to create two new arrays. It's the same basic idea in that we are essentially finding max values on both the left and right, and then determining the min of those two max values, as the min value is what caps the amount of trapped water that is possible.

We start this approach by initializing the variables we'll need:

let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let total = 0;

Here is a quick breakdown of what purpose each variable serves:

1. left - This variable serves as our pointer that will be incremented left to right.
2. right - This variable serves as our pointer that will be decremented right to left.
3. leftMax - Will always hold the most up-to-date max value from left to right.
4. rightMax - Will always hold the most up-to-date max value from right to left.
5. total - This is an accumulator variable that will hold a running total of the amount of trapped water we encounter.

Now that we have our needed variables, we enter our while loop. The condition of the while loop is while (left < right)- we want to avoid the pointers crossing each other, as that would be unnecessary extra work by checking values twice.

Now for the body of the while loop:

if (height[left] < height[right]) {
    leftMax = Math.max(leftMax, height[left]);
    total += leftMax - height[left];
    left++;
} else {
    rightMax = Math.max(rightMax, height[right]);
    total += rightMax - height[right];
    right--;
}

At each step we first check to see if height[left] < height[right].

If yes, we then take our current leftMax value and compare it to the current value at height[left]. We take the larger of the two values and assign it to leftMax. Reassignment happens regardless of whether the new value being compared is less than the current leftMax value or equal to it.

The next step is to take the current value at height[left] and subtract that value from leftMax. This tells us the maximum amount of water that could be trapped at that index position. We then add that value to whatever value is currently being stored in total.

Let's trace this on a real step from our example array, height = [0,1,0,2,1,0,1,3,2,1,2,1]. By the time the pointers reach left = 2 and right = 10, the running values are leftMax = 1 and rightMax = 1. Note that rightMax hasn't reached its true final value of 3 yet, because right hasn't scanned that far. It doesn't need to.

Here's why: height[left] = 0 and height[right] = 2. Since 0 < 2, we resolve the left side. We don't need to know the true tallest wall on the right side (which does eventually turn out to be 3, at index 7). We only need to know that whatever rightMax ends up becoming, it's guaranteed to be at least height[right] = 2, which is already bigger than leftMax = 1. That guarantee is enough to know leftMax is the ceiling here, no matter what.

So: leftMax = Math.max(1, 0) = 1. We subtract the pre-existing height at index 2, which is 0, from leftMax, giving us 1 - 0 = 1 unit of trapped water. We add that to total, then increment left by one spot.

The right pointer does not move on this iteration.

If the if clause returns false, meaning height[left] is not less than height[right], we enter the else clause instead. The logic is exactly the same, but instead of resolving height[left] we resolve height[right], and we decrement the right pointer instead.

As a final step, we return the variable total, which holds an accumulated value of water trapped in the whole array.

This approach also has a time complexity of O(n), but critically has a space complexity of O(1), as we are not creating any additional data structures to hold any values.

Conclusion

After sitting with these two approaches for quite some time, I am of the opinion that there is not a real advantage to ever implementing the naive approach. This is because I fail to see a real advantage to it. I don't think either approach has a readability advantage. The code for both definitely requires some documentation to make the logic clear, and the naïve approach requires two additional arrays. While that is nothing to be concerned about when the array size is 11, this approach clearly scales far worse as array sizes increase.