Container with Most Water
Vložit
- čas přidán 20. 10. 2018
- For business inquiries email partnerships@k2.codes Container With Most Water LeetCode coding solution. One of Facebook's most commonly asked interview questions according to LeetCode.
Coding Interviews Container With Most Water (LeetCode) question and explanation.
This question is a commonly asked by the following companies: Facebook,Google, Microsoft, Airbnb, Goldman Sachs, Alibaba, and Adobe.
Link to problem: leetcode.com/problems/contain...
Problem description: Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Intuition behind solution: O(n^2) compare every possible 2 pairs of vertical lines and continually update the maximum area. Two pointer approach: continuously move two pointers (that start at the beginning and end of the array) toward each other. At each iteration, calculate the area (updating the max area if necessary) and move the increment or decrement the pointer that is pointing to the smaller vertical line.
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / programeme
Follow me on GitHub: github.com/kdn251 Discord: bit.ly/K2-discord - Věda a technologie
Do you guys prefer me going through 2 different solutions? I.e. the "naive" approach and the improved approach?
yep
yes yes! the closer we get to actual interview scenario, the better it is
Please do that in all your videos, these are really help ful
yes
yes.. that works well
This is the most simplified explanation I came across! Thanks !
Anytime I'm happy it was helpful! :)
I like that you went through the brute force version first.
In the optimized example, the way I thought about it was moving the smaller wall in search of a bigger wall - keeping in mind that as we slide the smaller wall closer to the other wall we need an even higher wall to maintain our existing area or exceed it
Way better than I explained it lol thanks David!
Dude, this stuff is amazing. Not only easy to understand, but also gives me this cozy feeling of coding with my buddy. Subscribed
Love to hear that thanks Slava!
It's just awesome man. I couldn't understand the top rated solution on leetcode but yours is truly simple and well-explained. Best of luck!
Thanks Sohbet I'm happy that my video helped :)
Follow-up with this, with trapping rain-water..similar approach a few nuances...love to hear your take!
You're doing a great job ! Love your videos ! Really good explanations
You made this tough problem look so simple... I really wanna reach your level of coding..
Thanks man for this explanation. First example doesn't work properly if your input is {1, 1} or {1, 2} but second example is just brilliant
This is one of the best problems on greedy approach.
Nice video.
Thanks Soumya!
thank you, the way you explain when you code is really good
You are doing god's work my friend.
you make it look so easy .. please keep doing the good work thanks
Wooo thanks!! Been at this quiet some time, this video cleared it up.
Nachiket Lele happy to hear it! If you need help with other problems and interview prep in general be sure to subscribe to the interviewing service I created, The Daily Byte! I recommend joining the annual plan thedailybyte.dev/
I dont understand why most solutions dont consider the case when height[i] == height[j] more in detail. To me it doesn't make sense to jut decrement j when they are the same. Shouldn't there be another set of checker that will check in this case height[i+1] and height[j-1] and only choose the higher value one? Because when you decrement j, it could have been the case that it would have been better to increment i instead?
Yes i came up with this exact same optimal solution myself after thinking for 20 minutes. Woot woot.
Oh my God. Dude, you are amazing. It is the best explanation of algorithm I have ever seen. Subscription, like and all best wishes.
Great explanation! Thanks. Just not getting one thing. How are we incrementing i, if heights[i]
Heh, been solving leetcode for almost a month,this is the first one I got both of these solutions by myself,without any help. Big d.. energy!
Hi Kevin... You did a great job.. just a suggestion though - two pointer approach can do this in O(n) time :)
The moment I read the question, Kadane's algo just popped up into my head.
I was just wondering how this problem is related to Kadane. Would you mind giving some more details?
What happens when height[i] and height[j] are equal? Which pointer (i or j) would you increment in that case?
According to the code else part executes so right pointer(j) decrements
It also doesn't matter which one you change. Visualize a scenario where walls are of equal height. The ONLY way that you find a bigger container within those walls, is if there are two higher walls within the indices. If this is the case, then it doesn't matter whether you increment i or j, you will reach the solution either way.
Why only smaller need to be move whether its from right or left side ??
Two pointer technique is used when array is sorted right??
Can someone please explain how j & i pointers are related to the heights ?
What is the difference b/w this Q and *Largest Rectangle in Histogram* ?
Yo! Awesome dude. Thank you!
hi Kevin, Isn't be the minus of the heights at each index?
How does your bruteforce method pass the test case of continous incresing or descreasing numbers like suppose 1 2 3 4 5????.. answer should be 0 in this case and your approach will give 6 in this case.
amazing explanation
Why doesn't it matter what direction you move when both the left pointer and right pointer are the same height?
F me, I got a time limit exceeded doing recursion. I didn't think that you could just do 2 pointers, it makes sense now that I see it
bro, you don't mention the base case?
Is this question same as the Trapping rain water question?
OMG, i saw this as very big, because the difficulty level is medium, so i viewed it as very big and i got the approach since its medium I spent an other 3 hours for nothing, and then saw the solution and realised i should go through question twice
Did you end up getting it? LMK if I can help with anything!
@@KevinNaughtonJr Yes i did.. Thank you soo much for your videos.. I'm naive to leet code.. please include basic(brute force) followed by best approaches in your videos like you did now
@@saicharan8675 Awesome happy to hear it! I'll try my best to do that sometimes it slips my mind! I actually just uploaded another video if you're interested in watching the latest one! czcams.com/video/cQX3yHS0cLo/video.html
@@KevinNaughtonJr Thank you i will go through it..
I am not sure why this solution works when the height of the left and right are the same? How did we decide we can move only one side of container and hope to find the max area?
the same doubt killing me..plz mention if anyone finds the answer....thanks in advance.
@@byagnathavaasi
int fixConflict(vector& height,int s ,int e)
{
if(s>=e)
return -1;
int mymax=min(height[s],height[e])*(e-s);
if(height[e]height[s]){
mymax=max(mymax,fixConflict(height,++s,e));
}
else{
mymax=max(fixConflict(height,++s,e),max(mymax,fixConflict(height,s,--e)));
}
return mymax;
}
int maxArea(vector& height) {
return fixConflict(height,0,height.size()-1);
}
the basic idea that you will try recursively the both chances and get the maximum .
it would be a big help if you explain your approach on a whiteboard
cause your solutions are just awesome
Rajath Nayak thanks and I’ll see what I can do!
Awesome👏👏
When an if statement was the reason why your solution wasn’t passing all test cases
felted
damn these leet questions are so freaking hard lol
Didn't understand why you were doing, min * (j - i) in the brute force solution. Could you please elaborate if possible?
Mohan reddy lower of heights (because water would otherwise leak :D) * distance between two indexes in array
In the beginning, can we set max equal to 0?
I think that should be fine. I normally use something like Integer.MIN_VALUE so that the first time I calculate an area it's guaranteed to be larger and for error checking i.e. if at the end of the function if it's still equal to Integer.MIN_VALUE there's probably a problem.
In the second approach what if height[i] and height[j] are equal?
Why the second algorithm guaranteed to NOT missed the optimal solution?
Because you know that the width of the cylinder is constantly decreasing. Thus, the only other possible way to obtain a higher volume would to obtain a greater height, which is essentially what the second algorithm aims to do.
🔥🔥🔥
Hi Kevin, I have a question, why do we need have this step min*(j-i)? what's this useful?
min * (j -1) is what gives you the volume. the span of columns between j(right) and i (left) and the height of water (m) is your volume
can you please explain how you reach at this solution.......???
Optimizing for 2 parameters: decrease one only in pursuit of increasing other
Thnx :) It was helpful.
what if Height[i] and Height[j] is the same in the second option?
I meant "are the same" :-)
@@liutomzhi yep i have that qu3estion too. i dont know why you move the j pointer when both heights are equal.
why not move both pointers when they are both equal.
thats why we use
Because we want to maximize the result
Even though both heights are same we can't move both the pointer because if we do so we will miss the max possible ans
Because here we are greedily searching for the two maximum height which are at the larger distance ( to maximize the width).
Hope I answered your question.
What is the logic of using left and right indexes?
That's what's actually helping us walk through the different combination of containers (the left and right form the start and end of our container respectively).
According to you what percentage of coders are just ‘born with it’ as opposed to ‘worked their asses off to get good at it’?
One more approach, find the two maximum value from the array and find their index, now formula Is area = second-highest value (this is hight) *(index of first highest value - index of the second-highest value) (this is width), Note: here you need to subtract from highest index to lowest index
awesome !!!
max area can also be 8*8=64. Why was 49 selected as maximum area?
Hi Kevin , at 7.14 , what will happen if h[I]=h[j] ?
I have the same exact question, did you get the answer?
This is brilliant.
Thanks!
Good boy Kevin
The first solution was not accepted for me (time limit exceeded) ..
(Same algorithm but with C++)
That's because it was O(n^2)
Thanks.
Awsome
Cool
hi why we calculate (j-i) i'm so confused with this :( help me out
area = base * height, height is max value, base value will be the x axis, when you subtract j-i
why it works ?
It's a greedy approach where we use two pointers to continuously look for a container that would hold more water than we have currently found
Hey guy thanks for making these daily coding question interviews. I have a first round interview with Amazon sometime in the next 5-10 days. I've done about 85 easy level leet code questions so far. Could yo recommend a plan of attack on which questions to focus on? I hear they have 14 leadership principles. I want to be ready for the technical part too.
Oh yeah I should mention I've done all this questions in C++. Yikes :/
How was your interview?
@@marcelagomez9508 don't leave us hanging lol
for both who wonder what will happen if we have equal numbers basically we will try recursively both , it will be like this
int fixConflict(vector& height,int s ,int e)
{
if(s>=e)
return -1;
int mymax=min(height[s],height[e])*(e-s);
if(height[e]height[s]){
mymax=max(mymax,fixConflict(height,++s,e));
}
else{
mymax=max(fixConflict(height,++s,e),max(mymax,fixConflict(height,s,--e)));
}
return mymax;
}
int maxArea(vector& height) {
return fixConflict(height,0,height.size()-1);
}
This time you forgot the error checking at the beginning :D
It looks like you have just solved this problem again to make the video, like you already have solved this problem and learn the solution first and then make the video since you don't even think of check for testcases, and directly submitting.
amx!!
who is behind u ?
That's my girlfriend Carly :)
@@KevinNaughtonJr good, very beautiful.
@@ajourney179 Thanks!
I got the solution but I cant mathematically prove this is the optimal solution. Yikes
That's ok! I've never been asked to mathematically prove something during one of my interviews. I think a good way to try and prove that something is optimal is proof by contradiction...i.e. try think of a case where it won't yield the best possible result. I hope that helps!
@@KevinNaughtonJr Yep, I am currently trying to prove by contradiction and see where it goes. Many thanks, all the best to your channel
@@quocanhhbui8271 awesome lmk how it goes and thank you!