LeetCode 11: Container With Most Water

Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Constraints

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Examples

• Example 1:
  Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
  Explanation: The above vertical lines are represented by array [1, 8, 6, 2, 5, 4, 8, 3, 7]. In this case, the max area of water (blue section) the container can contain is 49.
• Example: 2
  Input: height = [1, 1]
Output: 1

Solution 1: Brute-Force

Steps

1. Use a nested loop to iterate through all possible combinations and continuously update the value of the maximum capacity max_water during the iteration.
2. Return max_water after the iteration is completed.

Codes

def container_with_most_water(height: List[int]) -> int:
    max_water = 0
    for i, left_bound in enumerate(height):
        for j, right_bound in enumerate(height):
            water = min(left_bound, right_bound) * (j - i)
            max_water = max(max_water, water)

    return max_water

Complexities

• Time Complexity: O(N2), where N is the length of the height array.
• Space Complexity: O(1)

Solution 2: Two Pointers

Thought

By observation, we can see that the main factor affecting the amount of water a region can hold is the lower of the two adjacent boundaries on each side:

Since our goal is to maximize water storage, we can improve search efficiency by continuously moving the boundary of the lower side during the iteration process.

Steps

1. Initialize the variable max_water as the current maximum water storage. Create two pointers, i and j, which start from the far left and far right of the array, respectively.
2. Continuously iterate while the left pointer i remains to the left of the right pointer j:
   1. First, calculate the water storage in the current range: min(height[i], height[j]) * (j - i).
   2. If the current water amount is greater than the current maximum water storage max_water, update it.
   3. Then, move the boundary of the lower side.
3. After the iteration is complete, return the maximum water storage max_water.

Codes

def container_with_most_water(height: List[int]) -> int:
    max_water = 0
    i, j = 0, len(height) - 1

    while i < j:
        water = min(height[i], height[j]) * (j - i)
        max_water = max(max_water, water)
        if height[i] <= height[j]:
            i += 1
        else:
            j -= 1

    return max_water

Complexities

• Time Complexity: O(N), where N is the length of the height array.
• Space Complexity: O(1)

References

• LeetCode link: Container With Most Water – LeetCode