Skip to content

11. Container With Most Water

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Brute Force (Nested Loop) Calculate the area for every possible pair of lines using nested loops. Keep track of the maximum area found. This approach is straightforward but inefficient. \(O(n²)\): Double loop to check all pairs. \(O(1)\): Constant space for variables only.
Two-pointer technique Use two pointers, one at each end of the array, to represent the lines. Calculate the area and move the pointer with the shorter line inward to potentially find a larger area. Continue until the pointers meet. This approach is efficient and leverages the idea that a shorter line limits the maximum area. \(O(n)\): Single pass as we move pointers inward. \(O(1)\): Constant space with only two pointers.

Implementation

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        max_area = 0
        while l < r:
            curr_area = (r - l) * min(height[l], height[r])
            max_area = max(max_area, curr_area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return max_area