👨‍💻 738LeetCode

Container With Most Water

Question

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.

Example

img

Solution

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

Comment

Smart sol.