Leetcode - 11: Container With Most Water
Given an array or heights we need to find two height between which the maximum water can be stored
What's the question?
Given n non-negative integers
a1, a2, ..., an , where each represents a point at coordinate
n vertical lines are drawn such that the two endpoints of the line
i is at
(i, ai) and
Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Let's see some examples
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
Instead of starting with a bruteforce solution for this problem as, we might have gone through the 2Sum and 2Sum-II problems wherein we use two pointers from the left and the right. We can use the same approach here.
We will start with a maximum area i.e.
0 and then as we initialize our pointers to start and end we will calculate the area
length * height.
length will become
right_ptr - left_ptr as each pole or line is at a distance of
1 unit from each other. But now because we have two pointers we will have to
choose either of the one height.
So to choose a height just imagine that if we choose a larger/bigger height out of the two then the water will start splilling from the smaller/shoter height pole so we should choose the
shorter pole. Now our area formula will become
(right_ptr - left_ptr) * min(height[left_ptr], height[right_ptr]).
Once we compute this area, if this area is larger than the current
maxArea we can replace the current
maxArea with the computed area. So after every left and right pointer iteration/change we can have
maxArea written as
maxArea = max(maxArea, (right_ptr - left_ptr) * min(height[left_ptr], height[right_ptr])).
Let's code this out
def maxArea(height): maxArea = 0 left_ptr = 0 right_ptr = len(height) - 1 while left_ptr < right_ptr: maxArea = max(maxArea, (right_ptr - left_ptr) * min(height[left_ptr], height[right_ptr])) if height[left_ptr] > height[right_ptr]: right_ptr -= 1 elif height[right_ptr] > height[left_ptr]: left_ptr += 1 else: left_ptr += 1 return maxArea
So that's it we did this in a single
while loop. The logic behind updating the
right_ptr is to move the either one when it's smaller than the other.
This way we can stay at a higher ground for one pole and keep on checking with different heights of other poles.
That's it for this blog, hope you found this helpful. You can connect with me on Twitter