Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). 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 n is at least 2.

Brute force

Find all O(n^2) possible boundary and find the max volume among all of them.

Moving the left and right boundary toward the middle

The container is formed by the left, right boundary and the bottom. The water level is determined by the smaller of the two boundary.

Increase volume

The only way to increase volume for a given container is to move the smaller boundary toward the center. If the new boundary is higher than the previous boundary and the new volume is bigger than the previous boundary, we just achieved an increase of volume.

Iteration

We use a while loop till the left and right boundary collapse. In each loop, we check if the current volume could be the max volume and move the smaller boundary toward the center.

    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        left_pt = 0
        right_pt = len(height) - 1
        max_area = 0
        curr_area = 0
        while(left_pt != right_pt):
            curr_area = (right_pt - left_pt) * min(height[left_pt], height[right_pt])
            if curr_area > max_area: max_area = curr_area
            if height[left_pt] < height[right_pt]:
                left_pt += 1
            else:
                right_pt -= 1

        return max_area

Why can’t we terminate early

I first tried to terminate the loop early if moving boundaries will not give us a higher volume. But this doesn’t work since we might just get stuck in a local minima. A case in point is height = [3,2,10000,1,1,10000,2,3]. We would just be satisfied with height[0] and height[-1] and never discover height[2] and height[-3].