11. Container With Most Water

Given $n$ non-negative integers $a_1, a_2, \cdots, a_n$, where each represents a point at coordinate $(i, a_i)$. $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, a_i)$ 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.

Solution: Two Pointers

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        low = 0
        high = len(height) - 1
        while low < high:
            if height[low] < height[high]:
                max_area = max(max_area, (high - low) * height[low])
                low += 1
            else:
                max_area = max(max_area, (high - low) * height[high])
                high -= 1
        return max_area

Related:

• 42. Trapping Rain Water