Leetcode 11: Container With Most Water

11. Container With Most Water 

  • Total Accepted: 99353
  • Total Submissions: 277586
  • Difficulty: Medium
  • Contributors: Admin

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.

 

Code

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

 

Idea

The time complexity is O(N). The idea is that if height[lp] < height[rp], then the bottleneck to determine the container volume is height[lp]. That means the container formed by height[lp] and height[rp'] for any rp' < rp must have smaller volume than that formed by height[lp] and height[rp]. In this case, lp should move to right.

You can easily deduct the other case: height[rp] < height[lp].

Reference: https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm

 

Leave a comment

Your email address will not be published. Required fields are marked *