[Solution]Problem 31:Maxium Rainwater Trapping[Microsoft]
Maximization, Problem Framing, Forward and Backward Passes
Happy Thursdays y’alls,
As promised here is the solution to the problem shared with you yesterday. Leetcode classifies this as hard, but you will see that with the method outlined here, you will be able to tackle such problems without struggling.
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
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can get a 30-day trial premium subscription for free using the link below-
Step 1: Reframing the Problem
This question can feel very overwhelming. A lot of the reason that Hard questions can feel unsolvable is that people just freeze up and don’t know where to start. This question is no exception. To solve this question, the first step is to understand what this question is asking. In detail. As they say, it’s hard to hit a target you can’t see.
We want to figure out how much rainwater a given configuration (list) can hold. Easy enough right? Let’s see if we can break this down even further, to a smaller problem. We know if we know how much water will be stored at an index, then we can just sum over all the indices.
It might seem like I haven’t done anything of value here. However, think again. We have gone from a bigger problem to a smaller one. We have also separated this problem into the hard (figuring out rainwater capacity of an index) and easy (summing over indices) components. We now have a good next step to go to calculate how much water will be stored at an index.
Step 2: Figuring out the Rainwater Mechanics
So how do we know how much rainwater is stored at one index? Let’s look at the provided input and its visualization. Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Let’s see if we can find any patterns for the amount of water being stored. Fortunately, this is a very normal scenario, so understanding it is not difficult.
I want you to notice the following things:
We can’t store any water at the 1st and last location. The water just flows away.
We can only really store water at an index when both the values on its left and right are higher. The maximum amount we can hold will be constrained by the minimum of the left and right values (excess water will just overflow).
We also have to account for the height of the current index. Thus our tentative system would look like this-
waterAtIndex= max(0, min(height[l], height[r])- height[index]). This makes sure we don’t store negative water at any given location.
The equation meets our common sense test. It is also a great indication of why foundational math skills will boost your performance in tech and interviews. Math at its core is about taking situations and turning them into systems that can be measured and quantified. Which is exactly what we did here.
Now that we have our basic system, let’s talk about the nuances. The first question in our mind should be how do we calculate the left and right indices?
It might be simple to just look at the immediate left and right of the indices and call it a day there. But that would be wrong. To understand that let’s take a simple example.
height=[5,2,0,2,5]
Look at index 2. If we took the left and right to be indices 1 and 3, we will get the water to 2-0=2. However, this is not true. We actually can save 5 units of water. Similarly, for index 1, we would say we can’t have any water if we looked at just the immediate neighbors (5 and 0), while we know we can save 5 units of water. This leads to our next insight. We want our left and right values to point to the largest values to the left and right of an index.
Step 3: A simple solution
We actually have done a lot of good work here. With all the analysis we have done so far, coming up with a solution is not too difficult. Here is what we can do:
Since we need to store the maximum left and right heights seen upto an index, we can create an array for each maxLeft and maxRight. maxLeft[i] would tell us the maximum height seen upto but not including the i index. maxRight[i] would tell us the maximum height from i+1, all the way till the end of the array.
If we did it the way described, then our time complexity would be O(n^2), since we would have to traverse the whole array for every index. We can bring it down to Linear time. To do so, we simply traverse the array once for the left side values and traverse the array in reverse to populate the maxRight. Then finally another traversal will be needed to calculate the water capacity of the cells.
As mentioned, using multiple arrays would take up extra space complexity. Is there a way to reduce our Space Complexity further? Using this technique, we can be reasonably sure that the time complexity will be O(n) at least. But is our space complexity bound to be Linear? Turns out there is an optimization we can use, called the Two Pointer Technique. I’m sure the more advanced among you were already thinking of it (my premium subs are all very smart). However utilizing it the correct way here is not a trivial task, hence the Hard Classification of this problem.
Step 4: Two Pointer Technique
The two-pointer technique is very useful in your coding interviews. It’s certainly one of the best techniques to have in your toolbelt.
The two-pointer technique is a simple idea. We take two pointers and place them somewhere in the list/array/data structure. We move the pointers when certain conditions are triggered. Two-pointers are a great tool to take advantage of certain special conditions in a problem.
The basic part of using the two pointers is pretty clear. We will use the two pointers to point to the max left and right max heights. The tricky part will be figuring out the mechanics of the two-pointer approach. For that, I like to use the following decomposition. This system makes figuring out Two-Pointer Implementations pretty straightforward. Learn it well to ace your tech interviews.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.