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.
Two Pointers. Start with the widest container, l = 0 and r = n-1. Say the left one is shorter, then this is already the largest container the left can possibly form. There is no need to consider it again, so we go to l = 1 and r = n-1. Similar for the other case.
class Solution: def maxArea(self, heights: List[int]) -> int: def computeArea(i, j): width = j - i height = min(heights[j], heights[i]) return width * height i, j, ret = 0, len(heights) - 1, 0 while i < j: ret = max(ret, computeArea(i, j)) if heights[i] < heights[j]: i += 1 else: j -= 1 return ret