[Solution]Problem 36: Container with Most Water[Two Sigma]
Get ready to make that Wall Street Money
AREEE YOUU REEADDYY?
As I mentioned yesterday, if you want amazing worker compensation, the Financial Sector is amazing. This is why I will start throwing in more questions asked by the Finance giants. We won’t ignore tech, just add the other sectors. Today’s solution will be on a question asked by Two Sigma, a big investment firm. Look at their salaries for software-
Let’s get right into the question. Get ready to make that finance money.
Problem
You are given an integer array height
of length n
. There are n
vertical lines drawn such that the two endpoints of the ith
line are (i, 0)
and (i, height[i])
.
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
You can test your solution here
[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 by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Only 15 days left in this offer -
Step 1:Sorting out the Details
This question is a little strangely worded. Perfect time for some clarifying questions. We can’t do that here, but just thought I’d leave it here as a reminder.
Let’s figure out the basics of what this question is asking. Essentially we want to maximize the area of a hypothetical rectangular container. What are the dimensions of the rectangle? All rectangles have 2 attributes
Width- The width would just be the difference between the location of the two lines we choose as our side. For example, if we choose the lines at locations 1 and 3, the width is 2.
Height/Length- This would be the minimum between the heights of the two lines we chose. For input [1,8,6,2,5,4,8,3,7], if we chose the first two, then the rectangle height will be min(1,8)= 1. We want the minimum, because if we chose the bigger value, then the water would simply spillover. This is similar to the problem Problem 31:Maxium Rainwater Trapping[Microsoft] which we have already covered.
Also remember, that the area of a rectangle is l*w. With all the baseline information out of the way, let’s get into a brute-force solution.
Step 2: Simple Solution
As always, we want to go to the low-hanging fruit first. In our case, the low-hanging fruit is a simple, brute-force solution that will compare all ideas for creating the rectangle. We will go one by one, checking different possible pairs of lines as sides. We can track the maximum and return the answer.
We will first create a triangle with the sides at index 0 and 1. Then we will check 0,2;0,3 … As you can see this is O(n^2).
However, that is not good enough. There is something better we can do. All the solutions/bootcamps/courses online will jump directly into the technique, without giving you the intuition as to why the technique is useful here. That is setting yourself up to fail. You will not gain any real benefits from just mindlessly memorizing patterns and techniques. Take a look at a message from one of my students who has benefitted from my approach-
Back to the solution, what is the technique? And why is this technique applicable here? Let’s get into it.
Notice that to maximize our area, we want to maximize both the length/height and the width. Why is this important? Look at the brute force solution. There is a very clear deficiency there. Look at the logic, and see if you can spot it.
Step 3:Optimizing the solution
Our brute force checks every possible combination. That much is obvious, but there is something it misses.
Our solution has two moving parts: the width, which we calculate as the distance between the two lines; and the height which is the minimum height between the two lines. We want both these values to be as high as possible. Maximum area is far likelier to occur with very high width.
Here’s the kicker. We know the maximum possible width. How? It’s going to be the container where we take the sides from the opposite end. It doesn’t make sense to not check that first, since we can find our maximum area much quicker by going through the high width options.
It’s pretty likely that we won’t find the solution immediately. We might have to search for other solutions if one of the ends has a very small height (Example 1). In such a case, we want to move inwards, since that still keep our width relatively high.
So an optimal solution at both ends. And the indices come up in towards each other, searching through the high-width options. Is this idea ringing any bells?
Step 4: Two Pointers
This is the technique I mentioned earlier. Other sources would just tell you to use the technique, and try to remember some pattern. However, by actually thinking through the question, we can come up with the solution in a way that is natural and will demonstrate your problem-solving abilities to the interviewers. Companies prefer candidates that can actually explain things, instead of simply reciting canned memorized patterns and solutions.
When we work on Two Pointers, there are a few details we want to figure out-
Where our two pointers start. We have already shown that we want to start at the ends and move inwards.
When our pointers move- Different questions will require different conditions for your pointers to move.
How much the pointers move. Some questions will see you move your pointers move more than one index per move. When implementing Two Pointers, don’t make the mistake of only moving one Pointer at a time.
So let’s figure out the details. Clearly, to have maximum area, we also want maximal height. Thus, when deciding between 2 pointers, it makes sense to move the one that has the lower height. This way, we’re taking advantage of the fact that area=l*w to filter out all solutions with low widths and/or heights. Neat, huh?
Obviously, we want to move our pointers only one step at a time. There’s no benefit to skipping over any potential side since there is no ordering in their heights.
Thus an algorithm would look like-
` ans = 0
l, r = 0, len(height) - 1
while l < r:
ans = max(ans, (r - l) * min(height[r], height[l]))
h0=min(height[l], height[r])
if height[r] > height[l]:
l += 1
else:
r -= 1
return ans
This will actually work if you put it into Leetcode. It is a Linear Time and Constant Space solution. However, this is still slow compared to what I’m about to show you.
What I’m about to show you will turn you from a “yes” to a very “strong YES!!!!”. It is crucial for all kinds of optimizations in interviews. And the best part is that the change is relatively simple. With some logic, we can actually filter out a lot more of the combinations, and make that sweet finance money.
Step 5: Final Solution
Here’s a cool little observation. If a>b then a> all numbers lesser than b. That should not come as a giant shock. Since one of my most engaged subs is named Artem, I will henceforth call this Artem’s Rule. This might seem silly, but this observation is the backbone of many optimizations. Now to get into how Artem’s Rule relates to this question.
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.