Jobs

Interviews

Discussions

Container With Most Water

#76 Most AskedMedium

Container With Most Water #76 Most Asked

Medium

PayPal

4 views

Topics:

ArraysTwo Pointers

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

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

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Try coding it in LeetCode

Container With Most Water

#76 Most AskedMedium

Container With Most Water #76 Most Asked

Medium

PayPal

4 views

Topics:

ArraysTwo Pointers

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

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

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the values in the `height` array, and can the heights be zero?
How many lines can we expect in the input array? For instance, what happens if the array has fewer than two lines?
Are the integers in the `height` array guaranteed to be non-negative, as implied by the term 'height'?
Just to confirm, the 'width' of the container is the difference in indices between the two lines, correct?
If multiple pairs of lines can form a container with the same maximum area, should I return any one of them or is there a specific preference?

Brute Force Solution

Approach

Imagine you have a series of vertical walls of different heights. The brute force strategy is to figure out the amount of water every single possible pair of walls could hold between them, and then simply pick the pair that holds the most.

Here's how the algorithm would work step-by-step:

First, pick a wall on the far left to act as one side of our container.
Now, pair this first wall with every other wall to its right, one by one, to form a potential container.
For each of these pairings, calculate how much water it can hold. The amount is determined by the shorter of the two walls and the distance between them.
Make a note of the largest amount of water found so far.
Once you've paired the first wall with all the others, move to the second wall from the left.
Repeat the process: pair this second wall with every other wall to its right, calculating the water for each pair and updating your record of the largest amount if you find a bigger container.
Continue this process, moving one wall at a time from left to right, and pairing it with all the remaining walls to its right.
After checking every possible combination of two walls, the largest amount you've recorded will be the final answer.

Code Implementation

def maxArea(height):
    max_water_volume = 0

    # Iterate through each wall to select it as the first potential side of the container.

    for left_wall_index in range(len(height)):

        # Now, pair the selected left wall with every other wall to its right.

        for right_wall_index in range(left_wall_index + 1, len(height)):
            distance_between_walls = right_wall_index - left_wall_index

            # The container's capacity is limited by the shorter of the two walls.

            container_height = min(height[left_wall_index], height[right_wall_index])
            current_water_volume = container_height * distance_between_walls

            # We must keep track of the largest volume found across all possible pairs.

            if current_water_volume > max_water_volume:
                max_water_volume = current_water_volume
    
    return max_water_volume

Big(O) Analysis

Time Complexity

O(n²) – The time complexity is determined by checking every possible pair of walls. Let's say there are 'n' walls. The outer loop iterates through each wall from left to right, serving as the first side of the container. For each of these 'n' walls, a nested inner loop iterates through all the remaining walls to its right to form the second side. This structure means for the first wall we do n-1 comparisons, for the second we do n-2, and so on. The total number of operations is the sum 1 + 2 + ... + (n-1), which is approximately n²/2, simplifying to a time complexity of O(n²).

Space Complexity

O(1) – The brute force solution operates by iterating through the input array with a pair of nested loops. To keep track of the result, it only needs a single variable to store the maximum area found so far. The amount of extra space required does not change as the number of walls, N, increases, resulting in constant space complexity.

Optimal Solution

Approach

The best strategy starts with the widest possible container and cleverly narrows it down. By always moving the shorter of the two sides inward, we can skip checking many combinations that are guaranteed to hold less water, quickly finding the largest possible area.

Here's how the algorithm would work step-by-step:

Imagine two pointers, one at the very beginning and one at the very end of the series of vertical lines. This forms our first, and widest, possible container.
Calculate the amount of water this container can hold. The water level is limited by the shorter of the two lines.
Remember this amount if it's the most we've seen so far.
Now, we need to decide which pointer to move inward to create a new, slightly narrower container. The key insight is to always move the pointer that is pointing to the shorter line.
Why move the shorter one? Because moving the taller one inward would definitely result in a smaller or equal area, since the width is decreasing and the height is still limited by that same shorter line.
By moving the shorter line's pointer, we give ourselves a chance to find a new, taller line that might make up for the reduced width and create an even larger container.
Repeat this process: calculate the area of the current container, keep track of the maximum, and move the shorter of the two lines inward.
Continue until the two pointers meet in the middle. The largest amount of water you remembered during this process is the answer.

Code Implementation

def max_area(height_of_lines):
    max_water_area = 0
    left_pointer = 0
    right_pointer = len(height_of_lines) - 1

    while left_pointer < right_pointer:
        left_height = height_of_lines[left_pointer]
        right_height = height_of_lines[right_pointer]

        container_width = right_pointer - left_pointer
        # The amount of water is always limited by the shorter of the two vertical lines.

        container_height = min(left_height, right_height)

        current_water_area = container_width * container_height
        max_water_area = max(max_water_area, current_water_area)

        # Moving the shorter line's pointer is the only way to potentially find a larger area.

        if left_height < right_height:
            left_pointer += 1
        else:
            # If heights are equal, moving either pointer works, as this width has been fully explored.

            right_pointer -= 1

    return max_water_area

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the two pointers, one starting at the beginning and the other at the end of the input array of size n. In each step of the while loop, we perform a constant number of operations: calculating the area, comparing heights, and then moving exactly one of the pointers inward. Since the pointers start at opposite ends and move towards each other, they will collectively traverse the entire array of n elements only once. The process stops when the pointers meet, resulting in a total of n-1 iterations, which simplifies to a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to solve the problem, regardless of the input size N. These variables include two pointers to track the container's sides and one variable to remember the maximum area found. Since the amount of extra memory used does not grow with the number of vertical lines, the space complexity is constant.

Edge Cases

Case	How to Handle
Input array has fewer than 2 elements (0 or 1)	No container can be formed, so the maximum water is 0.
Input array has exactly 2 elements	The only possible container is formed by these two lines, and its area is the solution.
All heights in the array are identical (e.g., [5, 5, 5, 5])	The optimal solution correctly identifies the widest pair (the first and last lines) as the one holding the most water.
All heights are zero (e.g., [0, 0, 0, 0])	The height of any container formed will be 0, so the maximum water capacity is correctly calculated as 0.
Heights are in a strictly increasing or decreasing order (e.g., [1, 2, 3, 4] or [4, 3, 2, 1])	The two-pointer approach efficiently narrows the search space by correctly moving the pointer at the shorter line inward.
Very large number of lines (e.g., 10^5 elements) with large heights	The area calculation (width * height) could result in a large number, which must fit within standard integer types like a 64-bit integer to avoid overflow.
Optimal container is defined by two very tall lines close together, surrounded by short lines	The algorithm correctly evaluates all potential containers, including narrow but tall ones, to find the true maximum.
Optimal container is defined by two short lines very far apart	The two-pointer approach starts with the widest possible container and guarantees this configuration is considered first.

Input array has fewer than 2 elements (0 or 1)

How to Handle:

No container can be formed, so the maximum water is 0.

Input array has exactly 2 elements

How to Handle:

The only possible container is formed by these two lines, and its area is the solution.

All heights in the array are identical (e.g., [5, 5, 5, 5])

How to Handle:

The optimal solution correctly identifies the widest pair (the first and last lines) as the one holding the most water.

All heights are zero (e.g., [0, 0, 0, 0])

How to Handle:

The height of any container formed will be 0, so the maximum water capacity is correctly calculated as 0.

Heights are in a strictly increasing or decreasing order (e.g., [1, 2, 3, 4] or [4, 3, 2, 1])

How to Handle:

The two-pointer approach efficiently narrows the search space by correctly moving the pointer at the shorter line inward.

Very large number of lines (e.g., 10^5 elements) with large heights

How to Handle:

The area calculation (width * height) could result in a large number, which must fit within standard integer types like a 64-bit integer to avoid overflow.

Optimal container is defined by two very tall lines close together, surrounded by short lines

How to Handle:

The algorithm correctly evaluates all potential containers, including narrow but tall ones, to find the true maximum.

Optimal container is defined by two short lines very far apart

How to Handle:

The two-pointer approach starts with the widest possible container and guarantees this configuration is considered first.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the values in the `height` array, and can the heights be zero?
How many lines can we expect in the input array? For instance, what happens if the array has fewer than two lines?
Are the integers in the `height` array guaranteed to be non-negative, as implied by the term 'height'?
Just to confirm, the 'width' of the container is the difference in indices between the two lines, correct?
If multiple pairs of lines can form a container with the same maximum area, should I return any one of them or is there a specific preference?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pick a wall on the far left to act as one side of our container.
Now, pair this first wall with every other wall to its right, one by one, to form a potential container.
For each of these pairings, calculate how much water it can hold. The amount is determined by the shorter of the two walls and the distance between them.
Make a note of the largest amount of water found so far.
Once you've paired the first wall with all the others, move to the second wall from the left.
Repeat the process: pair this second wall with every other wall to its right, calculating the water for each pair and updating your record of the largest amount if you find a bigger container.
Continue this process, moving one wall at a time from left to right, and pairing it with all the remaining walls to its right.
After checking every possible combination of two walls, the largest amount you've recorded will be the final answer.

Code Implementation

def maxArea(height):
    max_water_volume = 0

    # Iterate through each wall to select it as the first potential side of the container.

    for left_wall_index in range(len(height)):

        # Now, pair the selected left wall with every other wall to its right.

        for right_wall_index in range(left_wall_index + 1, len(height)):
            distance_between_walls = right_wall_index - left_wall_index

            # The container's capacity is limited by the shorter of the two walls.

            container_height = min(height[left_wall_index], height[right_wall_index])
            current_water_volume = container_height * distance_between_walls

            # We must keep track of the largest volume found across all possible pairs.

            if current_water_volume > max_water_volume:
                max_water_volume = current_water_volume
    
    return max_water_volume

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two pointers, one at the very beginning and one at the very end of the series of vertical lines. This forms our first, and widest, possible container.
Calculate the amount of water this container can hold. The water level is limited by the shorter of the two lines.
Remember this amount if it's the most we've seen so far.
Now, we need to decide which pointer to move inward to create a new, slightly narrower container. The key insight is to always move the pointer that is pointing to the shorter line.
Why move the shorter one? Because moving the taller one inward would definitely result in a smaller or equal area, since the width is decreasing and the height is still limited by that same shorter line.
By moving the shorter line's pointer, we give ourselves a chance to find a new, taller line that might make up for the reduced width and create an even larger container.
Repeat this process: calculate the area of the current container, keep track of the maximum, and move the shorter of the two lines inward.
Continue until the two pointers meet in the middle. The largest amount of water you remembered during this process is the answer.

Code Implementation

def max_area(height_of_lines):
    max_water_area = 0
    left_pointer = 0
    right_pointer = len(height_of_lines) - 1

    while left_pointer < right_pointer:
        left_height = height_of_lines[left_pointer]
        right_height = height_of_lines[right_pointer]

        container_width = right_pointer - left_pointer
        # The amount of water is always limited by the shorter of the two vertical lines.

        container_height = min(left_height, right_height)

        current_water_area = container_width * container_height
        max_water_area = max(max_water_area, current_water_area)

        # Moving the shorter line's pointer is the only way to potentially find a larger area.

        if left_height < right_height:
            left_pointer += 1
        else:
            # If heights are equal, moving either pointer works, as this width has been fully explored.

            right_pointer -= 1

    return max_water_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array has fewer than 2 elements (0 or 1)	No container can be formed, so the maximum water is 0.
Input array has exactly 2 elements	The only possible container is formed by these two lines, and its area is the solution.
All heights in the array are identical (e.g., [5, 5, 5, 5])	The optimal solution correctly identifies the widest pair (the first and last lines) as the one holding the most water.
All heights are zero (e.g., [0, 0, 0, 0])	The height of any container formed will be 0, so the maximum water capacity is correctly calculated as 0.
Heights are in a strictly increasing or decreasing order (e.g., [1, 2, 3, 4] or [4, 3, 2, 1])	The two-pointer approach efficiently narrows the search space by correctly moving the pointer at the shorter line inward.
Very large number of lines (e.g., 10^5 elements) with large heights	The area calculation (width * height) could result in a large number, which must fit within standard integer types like a 64-bit integer to avoid overflow.
Optimal container is defined by two very tall lines close together, surrounded by short lines	The algorithm correctly evaluates all potential containers, including narrow but tall ones, to find the true maximum.
Optimal container is defined by two short lines very far apart	The two-pointer approach starts with the widest possible container and guarantees this configuration is considered first.

Input array has fewer than 2 elements (0 or 1)

How to Handle:

No container can be formed, so the maximum water is 0.

Input array has exactly 2 elements

How to Handle:

The only possible container is formed by these two lines, and its area is the solution.

All heights in the array are identical (e.g., [5, 5, 5, 5])

How to Handle:

The optimal solution correctly identifies the widest pair (the first and last lines) as the one holding the most water.

All heights are zero (e.g., [0, 0, 0, 0])

How to Handle:

The height of any container formed will be 0, so the maximum water capacity is correctly calculated as 0.

Heights are in a strictly increasing or decreasing order (e.g., [1, 2, 3, 4] or [4, 3, 2, 1])

How to Handle:

The two-pointer approach efficiently narrows the search space by correctly moving the pointer at the shorter line inward.

Very large number of lines (e.g., 10^5 elements) with large heights

How to Handle:

The area calculation (width * height) could result in a large number, which must fit within standard integer types like a 64-bit integer to avoid overflow.

Optimal container is defined by two very tall lines close together, surrounded by short lines

How to Handle:

The algorithm correctly evaluates all potential containers, including narrow but tall ones, to find the true maximum.

Optimal container is defined by two short lines very far apart

How to Handle:

The two-pointer approach starts with the widest possible container and guarantees this configuration is considered first.

0/108 PayPal questions completed

0/108 completed