[Problem] Container With Most Water

leetcode.com/problems/container-with-most-water/

Problem Statement

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.

Example

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

For the example above, the highlighted red lines, each representing a height of 8 and 7, produces the greatest amount of which can be stored, with an total volume of 49.

Approach

These types of two-pointer problems involve a closer look into the problem, in an attempt to reach an intuition regarding the conditions for using two-pointer. First, when starting from the furthest endpoints, think how one point might have a higher height than the other. If we shift the point with the greater height, we won't benefit since the maximum height is determined by the smaller height.

However, if we shift the smaller height, there is a chance that we might benefit as there could be a higher corresponding height after the shift. Hence, we can solve the problem by always shifting the point with the lower height.

Solution

def maxArea(self, height):
        maxA = 0
        left = 0
        right = len(height) - 1
        
        while left < right:
            maxA = max(maxA, min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return maxA