menu

[LeetCode] 011. Container With Most Water

Problem (Medium)

011. Container With Most Water

Approach 1: Brute Force

Idea

We simply verify each possible pair of pillars for the container and save the max value.

Solution

class Solution1:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ret = 0
        for i in range(len(height) - 1):
            for j in range(i+1, len(height)):
                ret = max(ret, (j - i) * min(height[i], height[j])) 
        return ret

Complexity

  • Time: $O(n^2)$
  • Space: $O(1)$

Approach 2: Two Pointers Approach

Idea:

Set start and end pointers to narrow to the middle, using only one loop to find the maximum area.

Solution

    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ret, start, end = 0, 0, len(height) - 1
        while end > start:
            ret = max(ret, (end - start) * min(height[start], height[end]))
            if height[start] > height[end]:
                end -= 1
            else:
                start += 1
        return ret

Complexity

  • Time: $O(n)$
  • Space: $O(1)$



KF

Comments