The video effectively breaks down a complex coding problem into understandable steps, using a visual demonstration of the two-pointer approach. The creator's clear explanation and the practical application of the code make it valuable for viewers interested in competitive programming and software engineering.
Summary
The creator explains how to solve the LeetCode problem "Container With Most Water" using a two-pointer approach. They demonstrate the logic by iterating through the array with pointers at both ends, calculating the area, and moving the pointer associated with the shorter height inward to potentially find a larger area. The video concludes with the Python code implementation of this O(n) solution.
Structure
1Introduction to the LeetCode problem and the O(n) goal
2Explanation of the brute-force O(n^2) approach
3Demonstration of the two-pointer strategy with the example array
4Calculation of the initial area and the reasoning for moving pointers
5
Original caption
Which leetcode problem should I solve next? Leave me a comment! This is an awesome example of how to use two pointers to make a solution O(n). Feel free to ask any questions in the comments - there are no bad questions! I used @NeetCode to find this problem, and I’m writing my code in there. I’m using @figma to draw out my two pointer explanation! #leetcode #softwareengineer #coding #techtok #womenintech
More from @tarabyte.tech
Their other posts in the index, biggest breakout first.
Step-by-step walkthrough of the algorithm's logic
6Python code implementation of the two-pointer solution
7Explanation of the time complexity and why it's O(n)
8Call to action for engagement and follows
Product placement
The video features a screen recording of the LeetCode problem description and a Python code editor, with the creator explaining the problem and solution. The creator also mentions using Figma for drawing explanations and NeetCode to find the problem.
Call to action
Which leetcode problem should I solve next? Leave me a comment! Give me a follow and I'll make more teaching content
On-screen text
Container With Most Water
Medium
Company Tags
Solved
Medium
Example 1:
Input: height = [1,7,2,5,4,7,3,6]
Output: 36
area = 7
area = 36
Python
class Solution:
def maxArea(self, heights: List[int]) -> int:
winningArea = 0
leftIndex = 0
rightIndex = len(heights) - 1
while (leftIndex < rightIndex):
leftHeight = heights[leftIndex]
rightHeight = heights[rightIndex]
height = min(leftHeight, rightHeight)
width = rightIndex - leftIndex
area = height * width
if area > winningArea:
winningArea = area
if leftHeight < rightHeight:
leftIndex += 1
else:
rightIndex -= 1
return winningArea
Transcript
solve a leetcode with me taking a leetcode medium from O(n^2) to O(n) in the most efficient way. I'm Tara, I'm a senior software engineer and I used to teach computer science at Carnegie Mellon. So you are given an integer array heights where heights of I represents the height of the ith bar. You may choose any two bars to form a container. Return the maximum amount of water a container can store. Example 1: Input: height = [1,7,2,5,4,7,3,6] Output: 36. So when you see a problem like this, your mind might jump to trying out all possible containers and figuring out which one is the largest. And that would work, but that solution is O of N squared. And I made a video about how to write up that solution if you wanna check it out. But we can do better than that. And I'm gonna explain how. So let's take a look at the example array from the write up. If I'm going to consider the container with the maximum area, it has both the dimensions, a width and a height. And I'm gonna give myself the best shot of finding that container if I start off with the container that has the largest width. Putting the left bar at the very start of the array and putting the right bar at the very end of the array. And that's what I have in this example with these two pointers, one pointing to the beginning of the array and one pointing at the end of the array. And so we can figure out what this area is right here of this potential container, it happens to be seven. So the area here is seven. And that's because we have a width of seven, but we are constrained by the height of the left bar, which happens to be one. So now the question is, what other containers should we consider? Well, now I have the biggest width right now. And so any container that I look at in the future is gonna have a smaller width. And so if I'm going to decrease the width in any way, I should be looking to increase the height, right? Because that's the only way I'm gonna find an area that beats my current one. So in this case, we have a little height over here of one versus a bigger height of seven. And so we actually wanna move this pointer to the next one on the list in hopes of finding a larger height and thus a bigger area, even though we are sacrificing some width to do that. And if you actually compute the area of this particular one, it's the area that's shaded in blue from the example that happens to be 36. So the area here is 36. And in this case, we're like again, cool. I have a height of seven on this side, I have a height of six on this side. The only potential for finding an even larger container than this one would be if I could get an even bigger height. So that I could actually use this full seven on this side and that will be worth the sacrifice in the width by bringing these pointers closer to each other, right? And so in this case, I'm gonna move this pointer in. And so you see the algorithm basically is start your pointers at the very ends of the array. You're starting with the container that has the largest width, check that area. If it's the biggest area you've seen so far, great, keep track of that. And then we're gonna bring in whichever pointer is pointing at the smaller height, because you're always willing to trade a little width for a potentially larger height. And whenever the pointers meet each other or pass each other, that is when you are done looking at all the containers and you can feel confident that you have found the largest one. Now that we've talked through the solution, let's write the code. So we're gonna keep track of the biggest area we see so far in a variable, but then I'm also going to set up my left pointer, so I'm gonna call it left index, starting at zero and my right pointer, which is called right index, started at the last index in this list, which is the length of the list minus one. So the end condition for when we're done looking through our array is actually when the pointers catch up to each other. And so we're going to keep running this loop while the left index is less than the right index. So from here, we just have to get the left height and the right height at our two indices. So I'll just do that really quick. Left height is heights of left index. Right height is heights of right index. We talked about this before, but the actual height of the container is gonna be the minimum of these two. And then the width is just the difference between where our two pointers are in the array actually. So we can just do it like this. Width is right index minus left index. So now we need to calculate the area of our container and that is just the height times the width, as we remember from math class. Area is height times width. So we'll do if area is greater than winning area, well, we need to keep track of that. So winning area is equal to this particular area. Okay, so here's the most important part and this is the key that makes this O of N. We're gonna either move the left pointer in or the right pointer in. And so we do that until they reach each other. And so we're basically visiting each like element once. And so we are only running that loop of n times. I'm just getting back into teaching after a long break. So if you like the way that I teach, I would love to teach more leet code problems and fun computer science stuff. Give me a follow and I'll make more teaching content.
