#11

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Container With Most Water

Find two vertical lines that can form a container with the most water in a given array of heights.

Problem Statement

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]). The goal is to find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum amount of water a container can store.

To solve this problem, we need to identify the two lines that form the largest container possible by calculating the area between them. The area is determined by the smaller of the two heights and the distance between the lines. The challenge is to maximize this area while minimizing unnecessary calculations.

Examples

Example 1

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

Output: 49

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

Example details omitted.

Constraints

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

Solution Approach

Two-pointer approach

Start by placing two pointers at the beginning and end of the array. Calculate the area formed by the lines at these pointers and track the maximum area. Move the pointer pointing to the smaller line towards the other pointer, aiming to find a taller line that may increase the area. Repeat this until the pointers meet, adjusting based on the height at each step.

Greedy optimization

The greedy aspect comes into play when choosing which pointer to move. Since the area is limited by the shorter line, we always move the pointer pointing to the shorter line. This ensures that we focus on increasing the height of the container, which can only improve the area calculation.

Time complexity and space complexity

The time complexity of the two-pointer approach is O(n), where n is the length of the array, as we only traverse the array once. The space complexity is O(1), since we only use a constant amount of space to store the pointers and the maximum area.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) because we iterate through the array once with two pointers. The space complexity is O(1), as we only use a few extra variables for storing pointers and the maximum area.

What Interviewers Usually Probe

Do you understand the two-pointer technique and how it helps reduce the time complexity of this problem?
Can you explain why we always move the pointer pointing to the shorter line in the two-pointer approach?
Will you be able to implement the solution in linear time instead of simulating all possible pairs?

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution and instead using a brute-force approach that simulates all pairs, leading to O(n^2) time complexity.
Incorrectly assuming that we need to calculate the area for every possible pair, without leveraging the two-pointer approach for optimization.
Not updating the maximum area correctly when adjusting the pointers, potentially missing a larger valid container.

Follow-up variants

What if the problem includes additional constraints, such as a limit on the number of lines that can be considered for the container?
How would the solution change if the array elements were not restricted to heights, but had varying widths?
What if you need to find the maximum area of water contained between two specific indices, instead of any two lines?

FAQ

How does the two-pointer technique work in this problem?

The two-pointer technique involves starting with one pointer at the beginning and another at the end of the array, calculating the container area, and then moving the pointer pointing to the smaller line to potentially find a larger area.

Why do we move the pointer pointing to the smaller line?

We move the pointer pointing to the smaller line because the area is limited by the shorter line. By moving it, we try to find a taller line to increase the area.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of lines, because we only traverse the array once using two pointers.

Can this problem be solved in O(n^2) time?

Yes, but O(n^2) would be inefficient. A brute-force solution would check all pairs of lines, which is unnecessary when a two-pointer technique can solve it in linear time.

What is the space complexity of this problem?

The space complexity is O(1) because we only need a few variables for tracking the pointers and the maximum area, regardless of the input size.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $l$ and $r$ to point to the left and right ends of the array, respectively, i.e., $l = 0$ and $r = n - 1$, where $n$ is the length of the array.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            t = min(height[l], height[r]) * (r - l)
            ans = max(ans, t)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

Continue Practicing

#321 create maximum number #455 assign cookies #581 shortest unsorted continuous subarray