Bernice Waweru
Posted on February 14, 2022
Instructions
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The max area of water in the container can contain is 49.
Approach
Basically, this problem involves getting the area of a rectangle by multiplying the length and width.
We can initialize a left and right pointer where the left starts at the height[0] and the right starts at height[-1] to maximize the width.
We can then compare the right and left pointers and shift the one with the lowest value to attempt to increase the area by changing the height. We then update the maximum area as we shift the pointers.
Python Implementation
def maxArea(height):
left = 0
right = len(height) -1
max_area = 0
while left < right:
areas = (right-left) * min(height[left],height[right])
max_area = max(max_area,areas)
if height[left] < height[right]:
left +=1
elif height[left] > height[right]:
right -=1
else:
right-=1
return max_area
We can also implement the two-pointer approach as follows:
def maxArea(height):
# start looking from both ends of the array
l, r = 0, len(height) - 1
max_area = 0
while l < r:
if height[l] < height[r]:
area = height[l] * (r - l)
# height at the left is smaller so we should look for the larger heights by moving towards right.
l += 1
else:
area = height[r] * (r - l)
# height at the right end is smaller so we move towards the left.
r -= 1
if area > max_area:
max_area = area
return max_area
I hope you found this helpful
Posted on February 14, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.