Container With Most Water
DESCRIPTION (credit Leetcode.com)
Given an integer input array heights representing the heights of vertical lines, write a function that returns the maximum area of water that can be contained by two of the lines (and the x-axis). The function should take in an array of integers and return an integer.
EXAMPLES
Example 1:
Inputs:
heights = [3,4,1,2,2,4,1,3,2]
Output:
21
Example 2:
Inputs:
heights = [1,2,1]
Output:
2
Run your code to see results here
Solution
def max_area(heights):left, right = 0, len(heights) - 1current_max = 0while left < right:width = right - leftheight = min(heights[left], heights[right])current_area = width * heightcurrent_max = max(current_max, current_area)if heights[left] < heights[right]:left += 1else:right -= 1return current_max
Explanation
We can solve this question in linear time because we can eliminate containers as we search. After initializing our pointers at opposite ends of the array, the current container being considered is outlined in blue, which can hold a total of 16 units of water.
We get 16 by taking the width of the container right - left and multiplying it by the height of the shorter wall Math.min(nums[left], nums[right]).
Now, the question is: how can we advance to the next container in a way that eliminates unecessary containers from our search? Let's look at the volumes of all other containers ending at the right pointer (remember the volume of current container is 16):
And the volumes of all other containers starting at the left pointer:
All other containers ending at the right pointer hold a smaller amount of water than our current container, so we eliminate them from our search by moving the right pointer.
This gives us a new container with a volume of 21, which becomes the new maximum.
Loading comments...