Given n non-negative integers , where each represents a point at coordinate . vertical lines are drawn such that the two endpoints of line is at and . 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 is at least .
We are going to solve this problem using two pointers
l starts from the left-most side and
r starts from the right-most side. We then keep track of our
maximum = max(maximum, min(height[l], height[r]) * (r - l))
and then move one of the pointers based on the following conditions:
if height[l] < height[r]: l += 1 else: r -= 1
Let us explain the logic behind this algorithm using the illustration below.
For wall we want to use wall as its counterpart since is taller than and as far on the right as possible. Any wall to the left of can be ignored because it will only make our container smaller as is already taller than . That is why it doesn't make any sense to decrease our index
r. With and we have a container size of .
We then increment our index 'l' because is shorter than . That is, move it to wall in hopes that we can find a taller counterpart for our tall wall . Now, wall is taller than its predecessor and actually increases our container size to . We can see that since we previously increased the index pointing to the shorter of the two walls ( vs ) we were able to find a counterpart () for wall that increased our container size.
Finally we again increase our index pointing to the shortest wall in hopes that we may find an even taller counterpart for . Moving
l to we see that this does not increase our container size. Also since
r meet, we stop the search and return .
The full code is listed below.
class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ l = 0 r = len(height) - 1 maximum = 0 while l < r: maximum = max(maximum, min(height[l], height[r]) * (r - l)) if height[l] < height[r]: l += 1 else: r -= 1 return maximum