🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

@bhaskyOld

2 жыл бұрын

You didn't explain, why you are moving the minimum of the two pointers? What is the basis of this idea? Please do not take this other way, just a feedback from people like me who do not understand so easily. You are putting great effort. I feel there is a lot of logic behind incrementing the minimum pointer. We'll not get max area in any case , even if the next pointer is big, small or equal. This has to be explained I feel. Thank you.

@bricksnbuttons2000

2 жыл бұрын

Nick white is better

@rustemtehmezov9494

2 жыл бұрын

@@bricksnbuttons2000 then what are you doing here?

@abhijeetsinha8069

2 жыл бұрын

Why can't this be solved using monotonous stack ? Isn't this question same as 'Largest Rectangle in Histogram' problem in leetcode ?

@the_real_briel

2 жыл бұрын

@@bhaskyOld That's a good question, we should move the pointer with the lowest height because we are essentially trying to maximize both height and width. If we always drop the one with the lowest height, the height will only increase, with this intuition we will find the greatest solution as we will definitely encounter the point where both height and width are maximized, which reduces unnecessary checks. Does that make sense Bhasky?

I think a good explanation for why we move pointer with the lower height is because we already have the max area with that height - since it is the lower pointer that means that every other distance that is closer will always be a smaller distance with the same or less height which means smaller area. Therefore we do not need to look at every other combination with that pointer.

@raneisenberg2155

Жыл бұрын

Thanks, I was missing that part of the explanation

@tan-uz4oe

Жыл бұрын

@@Billych68 So, let i=0 and j=n-1, say we are considering a pair of vertical lines, h[i] and h[j], we know that the area of the current pair is maximum area for the shorter line (because the width is at maximum). Therefore, we can move the index corresponding to the shorter line inward. This process ensures that the outer lines (the ones to the left of i and to the right of j) has been checked for their possible max area. You can iterate this process on a paper and check the ones that has been maxed out. You will see that at any given i,j the area of the outer lines would be maxed out before we consider i,j. note: the process does not stop at i,j that gives maximum area, rather it iterates until i==j while keeping track of the maximum area.

@gto433

Жыл бұрын

This was so unintuitive damn. I was trying to sort the array to find optimal solution but got wrecked in edge cases. Anyone else thought this was unintuitive?

@mengdizheng1223

Жыл бұрын

yes when height[l] == height[r], no matter if r += 1 or l -=1, the area is always gonna be smaller in the next step . that's y we can do either .

@user-us2yn6js8j

Жыл бұрын

Great Explanation!

Dont go any further guys - This is the best channel for leetcode solutions ; Neetcode - you are the leetcode king

@CostaKazistov

2 жыл бұрын

For hard questions, I always watch Neetcode explanation first (as they tend to be shorter and clearer than others), and then often check how other KZreadrs explain by walking through DP solutions on a whiteboard. Medium ones Neetcode does really well. Hard ones are usually longer and tend to require more than one channel to fully understand the implementation. I've been doing easy and medium for a year now, only recently started doing hard problems. Neetcode will hopefully add more of the harder ones.

@mindsetnuggets

2 жыл бұрын

I agree. Hard questions made easy.

Explanation for equal heights edge case: Let's say we are at l, r where H = h[l] = h[r[. The recommendation would be to update both l and r. Why? The current computed area is A = H * (r-l). No other combination of h[i] and H s.t l < i < r can result in an area greater than A as the area would always be bounded by H i.e. H*(i-l) or H*(r-i) both of which are always smaller than A. Note by the time we reach this state of having equal height H, the max area with H as a boundary is either the current area A or already computed in a past iteration.

@ryukboredom2885

6 ай бұрын

Thanks for the explanation, this is the only part of the solution which I was a bit perplexed about

Whenever I always have a problem solving these interview questions, I always look at your videos first. I love the way you draw things out and help us visualize the problem. It's such a great way of understanding it. Thank you very much!

@NeetCode

2 жыл бұрын

Thanks, happy it's helpful! 🙂

If both heights are equal you can move both pointers because you're already bound to at most that height anyways so that max couldn't be any more than that position anyways since moving either pointer in will yield an area either less than or equal to the area at your current positions.

@pinakadhara7650

Жыл бұрын

Was looking for this! Thank you.

@ianokay

11 ай бұрын

He mentions flippantly "In this case it doesn't actually matter which pointer that we shift" 8:13 but I want to raise a question: What if the 3rd of the 4 bars between the 8s... is a 9 (instead of a 5)? The 9 would of course be 3 spaces away from the L->8, but only 2 spaces away from the R->8 So then, the "L and R same size edge case" arbitrary choice of always shifting the left does matter, right? Because, imagine we're on 8L and 8R: If we shift left we only ever see 9L to our 8R, right which is 8x2. If we shifted the right however we would see 8L and 9R, which is 8x3. Depending on the direction you shift you never get to one of the computations. I'm having trouble wrapping my head around how it can possibly not matter, or where my logical error is.

@ianokay

11 ай бұрын

*This is an absolutely CRUCIAL comment to this problem that actually makes this video problematic in not having it*. 8:12 It is the KEY, pivotal point in this entire exercise, and illustrates how even an expert like the @NeetCode author can miss a pivotal point and craft and algorithm that demonstrates not understanding the fundamental axiom of the whole question. Moving just one pointer arbitrarily shows a lack of understanding this core concept of the equation, and why you're doing what you're doing, and where you currently stand in the equations execution in which you must author its next choice. Many entire questions boil down to this exact choice. It absolutely does matter which pointer you move, because they ARE NOT equal, as you will cover some paths and not others depending. However, it also DOES NOT matter which you move, and you instead should just move both (if you truly understand), because of the fundamental tenant @ChristopherPerry keenly has considered, grokked, and outlines.

@rootr00t

11 ай бұрын

@@ianokay let's say you have a really tall bar between the 8s, but that still be bound by one of the 8s because we compute area by min height. That's why it doesn't matter which pointer to move. However, if you have 2 really tall bars between the 8s, eventually loop will reach to both of them, because if let's say left pointer reached the first tall, from this point only right pointer will move left until it reaches 2nd tall.

@shonoma

7 ай бұрын

@@rootr00t Amazing explanation, thanks!

amazing how you explain almost every code with such ease and such clarity

I have been following your roadmap, and it really help me learn a lot. As your roadmap group the same type of questions together, I know this is a two pointers problem and solve this question by myself. Coming from someone that has no idea whats going on in any leetcode questions, to doing a medium question alone, I feel so good and thanks again for the roadmap!

I've been following your roadmap and this was the first medium problem i was able to come to the same solution as you did on my own. I'm super happy to see myself progressing! Thanks for the videos!

Couldn't help but take a moment to leave a comment on this. It has been a long time goal of mine to become a better programmer through practicing leetcode questions but I always felt super defeated when I would try random questions from leetcode and make little to no progress. Neetcode has given me a way to incrementally improve my knowledge and show real progress. For the first time I am solving leetcode questions on my own. Disclaimer it is very rare that I solve them on my own my first try but it is happening more often as I progress. Thank you Neetcode!!!

Your leetcode videos are my favorite because you don't jump straight into code. You start with the most basic solution and show us how to refine our thought process to find the optimal solution. Thanks for all you do!

Thank you so much for creating this channel! My method in the past to studying algorithms was to just try to figure it out myself, sometimes getting stuck for a day. I've been watching your videos and I find it very helpful listening to you break down a problem with easy to understand pseudo code and then trying to implement the solution in code myself (without looking at your coded solution).

I have more gratitude now for seeing this video finally! Thanks a lot NeetCode for such great explanation. This question was asked in Microsoft interview and I had hard time understanding the problem (histogram) and coming up with solution back then in 2019. I had searched n-videos which had poor explanation and complex solution. You made my day ! I cannot thank more

@NeetCode

3 жыл бұрын

Thanks! I'm Really happy it was helpful 😃

This is the first problem I was able to solve with 0 help, and 0 bugs first try. The runtime was faster than 94%+ and Space better than 97%+. All of this was because of the explanation videos you provide for all of these problems :). Thank you for these.

I love you man. I have been trying to learn how to solve leetcode problems for 3 years and I came up dry. Then I came across your videos and they helped me more than anything else. You inspired me to share my knowledge. That is why I started my channel. Thank you very much again. If I ever come to seattle (I think you live there) I will take you to lunch.

Great explanation. This is a type of problem which don't have any complicated edge cases and is very easy to understand at first read (perfect for interviews) but the optimal solution is quite subtle.

This is incredible youtube channel with such incredible videos. I have been thinking on this problem for a week, I actually knew your video but I wanted to get right point myself. My only mistake was I have been moving pointers when new maximum result is bigger than previous one but now I saw your technique and I say myself why I didn't watch video earlier. Your channel helps me lot, thank you very much!! Keep up this good work!

I hope to get better at solving problems like you do! keep up! I love your content and explanations

I have managed to learn how you approach problems and tried my hands on this problem and was able to solve the first try. Thank you so much for these videos, mean a lot!

This is the point 6:40 I was looking for in the optimal solution on how to move the pointers - Thanks for the explanation

@robinfelix3879

2 жыл бұрын

Exactly !. Same point i got struck hehe. Happy to see Many of them here are in same page 😇

Very clear and intuitive. Thanks for the work!

@NeetCode

3 жыл бұрын

Thanks!

I attempted to solve it on my own and was soooo close to the solution but off by a misplaced if-else statement. Solved it in a second after you mentioned to move the pointer from the minimum height. Thank you for all you do!! Today is a day I feel smart while coding lol.

Thank you for starting with brute force approach. This is how all KZread videos should be. Discuss various approaches, evolution and trade offs.

Amazing explanations in all of your videos. This particular problem was so much clear with your video. Keep up the good work. That is awesome!!

@NeetCode

3 жыл бұрын

Thanks 😊

Great solution! There is an optimization. When height[left] height[left] to avoid unwanted calculations.

@the_real_briel

2 жыл бұрын

This is a great optimization, I wonder if the additional check usually ends up being worth it however, as there are some cases where this may not reduce any calculations.

@samuraijosh1595

7 ай бұрын

cant we do the same for height[right] isnt' a simple arithmetic calculation very negligible in terms of cost?

thank you man, hope for you all the good. please keep helping us

Thanks for awesome work, man! I was initially slicing the target array by left and right pointers to get its' length, but when I saw your method of getting the area I realized how dumb my way was :)

Great explanation, I was able to code it in Java both Brute Force and Two Pointer solution because of the easy to understand explanation.

Brilliant as usual ) Thanks for suck an amazing explanations!

Thanks for always making us better at algorithm thinking! The linear algorithm is similar to the Valid palindrome Two pointer solution we used, right?

Thank you for the clear explanation. Great Job!

Thanks for your kind video. :) now I can solve the problem.

Although there are some good explanations already on why we move the pointer with the lower height inward, here is another perspective. The objective of the problem is to maximize min(heights[a], heights[b]) *⋅* (b - a). We start off the problem with the pointers at the edges. If either pointer moves inward, that second term (b - a) is always going to decrease, so that is out of our control. But if we move the higher-height pointer inward, the first term min(heights[a], heights[b]) can only decrease or remain fixed. To see why, note that there are two cases: 1) The higher-height pointer reaches an even higher height-since we are taking the min, the term will remain the same; 2) We reach a lower height-then the term may either stay fixed or decrease if it is lower than the other pointer's height. On the other hand, moving the lower-height pointer inward, there are once again two cases: 1) The lower-height pointer reaches a higher height, then the term will always increase; 2) We reach a lower height, then the term decreases. So in order to maximize the first term, min(heights[a], heights[b]), we must move the lower-height pointer inward, as moving the higher-height pointer inward yields only decreases (or fixed). (note that the second term (b - a) is ensured to be as max as it can as we start the pointers at the edges, and move inward (thereby decreasing the term) to check for potential maximums, while keeping a max variable).

@noextrasugar

9 ай бұрын

This explanation helped me finally understanding it completely, thank you!

@devarapallivamsi7064

6 ай бұрын

Excellent!!! Thanks a lot.

@TJ-qv8rx

3 ай бұрын

Good explanation! Thanks!

@WhyAnkurGautam

Ай бұрын

Thanks

@marmrmaaat512

Ай бұрын

Thank you! Your explanation helped me to finally understand this question!!

I can see the algorithm gives us a local optimum because it is greedy. But why the local optimum is guaranteed to be the global optimum?

@amarnathprasad9986

3 жыл бұрын

Adding to your question, how did you figure out that a greedy approach was to be used?

@hadeeltantawy3244

3 жыл бұрын

I have the same question, what guarantees that a greedy solution will give global optimal?

@PippyPappyPatterson

2 жыл бұрын

@@hadeeltantawy3244 @Nikola Huang I'm not 100%, but I think it has something to do with the fact that the smaller of the two heights limits the total area. I'd love to have a full explanation though too. Even if I had come up with this idea on my own upon first encounter, I think I would quickly dismiss it because I'd think it might miss the global optimum.

@bananamuffin4286

2 жыл бұрын

Hi, I think the reason why this approach works is that for every width, we're trying to maximize the area and then find the maximum of all those areas. For the l=0 & r=arr.size()-1 we only have one solution possible, but after this for every width we have multiple solutions possible and so we greedily try to pick the maximum minimum pointer as that will be the limiting factor for any given width.

@davidespinosa1910

8 ай бұрын

I see, by "greedy", you mean that res is always increasing. Good questions !

Thank you for a clear explanation and also showing brute force and an optimized version.

Great video, I am trying to understand the difference between this problem and the 42.tapping rain water problem.

In case both heights are equal and after calculating the area, shouldn't we move both sides ? as there is no other area would exceed that area with one of them as a side (even if the new side is taller) and smaller length in between

hello! what if at the 8:30 mark the tallest column is left to 8 (say 20) ? the max product would be 6 * 20. but we move to the right of 6 - and lets say everything to right of 6 is much smaller. so we never computed the max ? I think the movement to left and right should not be dictated by the lower of the two heights (rather by the delta of the two new possibilities compared to current area). because even shifting to the left of the greater height can yield the max (if this delta is quite positive).

@drstoneftw6084

2 жыл бұрын

it wouldn't be 6 * 20, rather min(6,20) * distance. So it doesn't matter if we shift to the left or right. If the value is smaller, 10 would be the optimal choice, if it's bigger we shift on the other side next which gets us 20 example 1: [1,10,6,2,5,20,10,3,7] we start by shifting right: 6 and 10 and so on still smaller, we start by shifting left: 20 and 10 => still 10 and 10 bigger. example 2: [1,10,30,2,5,20,10,3,7] we start by shifting right: 30 and 10 => still smaller. we shift left since 30 > 10, 30 and 20 new max. we start by shifting left: 20 and 10 => still smaller. we shift right since 20 > 10, 30 and 20 new max. tldr: shifting right or left in case equal doesn't change the result.

Best explanation out there. Thank you!

Super proud of myself for solving this one on my own! This was really tough

Awesome explanation. Very clear

I'm so excited that I solved this problem just now. And my idea is the same as yours. The only difference is the variable names. Lol Anyway, thank you for providing so many good videos. I've learned a lot.😀

For these types of problems, is there any pattern we could learn other than just using two pointers? This problems just seems like you either can figure out what you need to do or you don't figure it out and fail. Is there any recommendation, on how I could approach these types of two pointer problems and get better at them?

Awesomely explained !! Please keep making videos like these.

@NeetCode

2 жыл бұрын

Thanks, for sure!

We could further optimize it by keeping track of the current left max and right max, dont do any calculation if new left or new right is smaller than the cur left or right max

thank you for the great and clear explaination!

@NeetCode

3 жыл бұрын

Thanks, happy it was helpful

top tier solution thanks!

awesome stuff man!

On the edge case where the array values of the two pointers are equal, why does it not matter whether you increment the left pointer or decrement the right one? Here's why: Because whichever one you choose, the other "side" of the container is going to be that previous height. So the new area is always less than or equal to the old area (since if you increment L to a larger value of decrement R to a larger value, it's mitigated by the fact that we can't overflow the container!) Thus it doesn't matter.

Hi NeetCode, thank you for the video, please don't stop :)

@NeetCode

3 жыл бұрын

Thanks!

Great video and explanation! Subscribed!

@NeetCode

3 жыл бұрын

Thanks, appreciated =)

Truly the OG in LeetCode problems

Dude you are amazing! Thank you so much 🥰

I love you neetcode, you're the best!

Thank you! Amazing explanation

I solved this problem on my own after you explanation. Thank you so much.

¡Excelente explicación!

This was so good , thank you.

@NeetCode

3 жыл бұрын

Thanks! Glad it was helpful!

What is the thinking pattern to come up with such solutions? I figured two pointer technique but couldn't figure out what condition to set to move the pointers. I have been bugging my mind whole day :(

I always felt daunted by the problem, but its actually quite easy

My good,, i was literally suffering from the solution of other youtubers,now understood crystal clearly.❤❤

Thank you. I understood the algorithm at 6:55

Thank you for your video! May I know the space complexity for the optimal solution?

Perfectly explained. Only had to watch once to completely understand what is going on which never happens lol

great explanation!!!!

Yo this was soo good! Thank you !!

@David70154

3 жыл бұрын

Lol but the bruteforce method was accepted on my leetcode. I guess i should learn both though just incase.

i think after several arrays problem, one has picked up the two pointers technique. but for this particular problem, all the signs like big array input that requires faster running time that O(n^2) and the max product is based on multiplication of two numbers in the array requires retrieval of two numbers in an array hints at using the two pointers technique even more

Hey I have been trying to practice these for sometime now, wanted to check do we get these kind of solutions on one go? Like how much time do we spend on questions till we get a solution like this? The solution seems so elegant, but how do you even come up with this in first go?

Ugh, I hate that I need to look up some of these solutions, feels like I've been defeated :( Thanks though lol.

@mathewlathra1900

2 жыл бұрын

Same here

Thank you so much dude...

really helpfull and the explanation is too good thank you ....

Good job bro!

By seeing the problem statement, i taught solution will be very difficult , but the way you explained now i can feel problem was very simple and easier to solve Thanks for explanining in simpler way

Thanks for great explanation. I can follow along once we decide l=start and r=end. I was stuck with l=start and l=start+1. How to decide where to place the 2 pointers initially?

Thanks my guy!

im starting to get the same exact solution before even watching the video. neetcode is the goat

Thanks a lot!

Thank you!

Thanks bro, liked

best explained!

great explanation

Is it worth keep updating the pointer until we get the height that is larger than current one? left = height[l] right = height[r] if left

Ive watched all your videos for all your neetcode150 and really amazing stuff. I didn't know where to post this but I just have one thing I needed to point out. the solutions coded in python are great, but who ever was in charge of posting the solutions in javascript did a beyond awful job. im talking like truly truly horrible, to the point it would get me extremely frustrated as an interviewer to see a candidate write code that way. The person rights drastically more than needed, and while sometimes thats good if it makes the code more readable, the opposite actually is true. a 7 line solution in python for some reason has several different functions in javascript that are a mess and confusing to follow. Im honestly happy to redo the javascript solutions for you, but wanted to at least call it your attention. whoever did it, did a really awful job. anyways your explanations are top notch. thank you.

Amazing, easy!

I don't full understand how this works. How are we able to skip all the combinations and be certain that the omitted combinations won't work? For example 9:32 the combination of 7 and 6, and many others, were never examined. So what's the "magic" where this algorithm will work by skipping iterations of all combinations?

Notice if the new height is smaller than the previous height, then we can skip that height. def maxArea(self, height: List[int]) -> int: res = 0 l, r = 0, len(height) - 1 preL, preR = 0, 0 while l if preL > height[l]: l += 1 continue if preR > height[r]: r -= 1 continue area = (r - l) * min(height[l], height[r]) res = max(res, area) if height[l] preL = height[l] l += 1 else: preR = height[r] r -= 1 return res

Awesome man

Thank you. :)

Would it be ok to increment L and decrement R if the heights are the same?

Thanks!

I'm actually curious what program or accessory you use to get those nice see-through brush drawings on the screen. Care to share? Peace.

i couldn't even understand the question itself cuz it was so unnecessarily unclear but I do now, Thank you neetcode

ok but i have a question. I wrote the same code but with a for look in the range(len(heights)) and it ran much faster than your code. why does the while loop make it much slower? [for context, for loop runs faster than 96% of all pythons solutions, where as the while loop one runs faster than just 10%)

I could not figure it out, but after watching this video solution. It turns out that the solution was actually pretty simple and easy to understand, I makes me wonder why I could not think of it.

Is there anyone who can prove why this works? Not sure how I’ll come with such solutions in interview settings. :)

@PippyPappyPatterson

2 жыл бұрын

^

@sachinfulsunge9977

2 жыл бұрын

He literally did, you calculate the max length and width from left to right and keep updating the max value. What I tried was starting with the max value and the second max value then calculating the width lmao I am trash

@sachinfulsunge9977

2 жыл бұрын

I don't think the interviewer expect a perfect solution for the question he wants to see how the candidate thinks and approaches the problem

This is my 45th question which i solved and am comfortable with medium array question now still struggling with hard but the point is if your channel didn't exist learning wouldn't have been so easy for me really thanks man keep going.

@faizaanshaik3007

3 күн бұрын

Did you solve just by seeing question or after watching approach

can anyone help me with the pointer shifting logic? I didn't understand the logic of shifting the left and right pointers.

i wish i could give you a hug for making these videos

Can someone explain why my pointer advancing logic is incorrect? I can see it is not working but I don't understand why. When incrementing the pointers, I look for the next area that both cases return and pick the greater one. For example, if the left pointer is advanced what is the area I get, and if the right pointer is advanced, what is the area I get and I pick the one that returns greater area.

thanks!