LeetCode 11: Container With Most Water

Problem Description

Difficulty: Medium

You are provided with an integer array height, where each element represents the height of a vertical line at a specific index on the x-axis.

Find the two distinct lines that, along with the x-axis, form a container capable of holding the maximum amount of water.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Explanation: In this case, the maximum area of water the container can contain is 49 (7 x 7). The height of the container is 7, governed by the shorter of the two lines of height 8 and 7, and the width between these two lines is 7. The container with height 8 on both sides has a width of 5; thus an area of 40 (8 x 5), which is not the maximum possible.

Example 2:

Input: height = [2,2,2]
Output: 4

Constraints:

# NeetCode:
2 <= height.length <= 10^3
0 <= height[i] <= 10^3

# LeetCode:
2 <= height.length <= 10^5
0 <= height[i] <= 10^4

Initial Solution

from typing import List

class BruteForceSolution:
    def maxArea(self, heights: List[int]) -> int:
        max_area = 0

        for x1, y1 in enumerate(heights):
            for x2, y2 in enumerate(heights):
                if x1 == x2:
                    continue
                area = (x2 - x1) * min(y1, y2)
                max_area = max(area, max_area)

        return max_area

heights1 = [1,8,6,2,5,4,8,3,7]
heights2 = [2,2,2]
solution = BruteForceSolution()
assert solution.maxArea(heights1) == 49
assert solution.maxArea(heights2) == 4

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        max_area = 0
        l = 0
        r = len(heights) - 1

        while l < r:
            area = (r - l) * min(heights[l], heights[r])
            max_area = max(max_area, area)
            
            if heights[l] < heights[r]:
                l += 1
            else:
                r -= 1

        return max_area

heights1 = [1,8,6,2,5,4,8,3,7]
heights2 = [2,2,2]
solution = Solution()
assert solution.maxArea(heights1) == 49
assert solution.maxArea(heights2) == 4

Initial Results

My inital brute force solution passed NeetCode. However, with \(O(n^2)\) time complexity, it’s insufficient for LeetCode. The next attempt was a two-pointer solution, with worst-case complexity of:

• Time complexity: \(O(n)\) as the pointers traverse the input list only once
• Space complexity: \(O(1)\) as no additional space is used that would grow with input size

NeetCode Solution

NeetCode’s solution is basically the same as that shown above. To be fair, I originally had if, elif, and else statements for the <, >, and == conditions, but as the outcomes of the elif and else branches were exactly the same, they could be combined.