Containers with most water [LC#11]
Given
non-negative integers , , … , , where each represents a point at coordinate . vertical lines are drawn such that the two endpoints of the line is at and . Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Two pointer approach
- Given 2 walls, the volume of water between them is limited by the smaller one. So we can move inwards from the smaller wall.
- This can be implemented using a 2 pointer approach closing in from both ends.
def max_water(height: List[int]) -> int: left, right = 0, len(height)-1 max_area = 0 while left < right: max_area = max( max_area, (right - left)*(min(height[left], height[right])) ) # we have to move away from the smaller wall # as it is limiting factor of the area if height[left] < height[right]: left += 1 else: right -= 1 return max_area