Container With Most Water

Question Description

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.

Solution

For $$a_i < a_j$$, if we move $$a_j$$ backward, the water contained will be not more than $$min(a_i, a_j) * (j - i)$$ because of $$min(a_i, a_j) >= min(a_i, a_k), i < k < j$$. So we only need to move the smaller side forward or backward every time to get a possible bigger potential result.

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