Jobs

Interviews

Discussions

Container With Most Water

Medium

Container With Most Water

Medium

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 maximum size of the `height` array? Is it small enough to fit comfortably in memory?
Can the values in the `height` array be zero or negative?
If the `height` array is empty or contains only one element, what should the return value be?
If there are multiple pairs of lines that produce the maximum water, is any one of them acceptable?
What is the expected return type (e.g., integer, float) and should I be concerned about potential overflow issues with large heights and widths?

Brute Force Solution

Approach

The brute force approach to finding the container with the most water involves checking every possible pair of vertical lines. For each pair, we calculate the area of the container they form. We then keep track of the largest area found so far and ultimately return that maximum area.

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

Consider every possible pair of lines from the set of lines you have.
For each pair, determine the shorter line, as this limits the height of the water the container can hold.
Calculate the distance between the two lines you're currently considering. This is the width of the container.
Multiply the height (the shorter line) by the width (the distance between the lines) to get the area of the container formed by that specific pair of lines.
Compare this area to the largest area you've seen so far. If it's bigger, update the largest area.
After checking every possible pair of lines, the largest area you've kept track of will be the solution.

Code Implementation

def max_area_container_brute_force(heights):
    max_area = 0

    # Iterate through all possible pairs of lines
    for first_line_index in range(len(heights)):
        for second_line_index in range(first_line_index + 1, len(heights)):

            # Determine the height of the container
            # formed by the current pair of lines.
            shorter_line = min(heights[first_line_index], heights[second_line_index])

            # Calculate the width of the container
            container_width = second_line_index - first_line_index

            # Calculate the area of the container
            current_area = shorter_line * container_width

            # Keep track of the maximum area found
            if current_area > max_area:
                max_area = current_area

    return max_area

Big(O) Analysis

Time Complexity

O(n²) – The algorithm considers all possible pairs of vertical lines. Given n lines, the outer loop iterates through each line. The inner loop iterates through all the lines to the right of the current line in the outer loop to form pairs. Therefore, for each of the n lines, we perform operations proportional to n in the worst case. This results in roughly n * n/2 comparisons and calculations, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force approach only uses a few variables: one to store the current area, one to store the maximum area found so far, and potentially loop counters. These variables take up a constant amount of space, irrespective of the number of vertical lines (N). Therefore, the algorithm's space complexity is constant, or O(1).

Optimal Solution

Approach

The core idea is to find the largest possible container formed by two vertical lines. We begin by considering the widest possible container and then iteratively narrow it down, always moving the shorter of the two lines inward, since this is the only way to potentially find a taller container.

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

Begin by examining the outermost pair of vertical lines.
Calculate the amount of water held within the container formed by these lines. This amount is the container's width (distance between the lines) multiplied by its height (the shorter of the two lines).
Now, consider which line to move. Move the shorter line inward. The idea is that moving the shorter line has the potential to increase the height of the container.
Calculate the water contained by the new container (formed by the new line and the previous taller line).
Keep moving the shorter line inwards, continually calculating the water that can be contained, and always remember the largest amount of water we have seen so far.
Repeat the process until the two lines meet. The greatest amount of water we remembered during this process is the answer.

Code Implementation

def max_area(heights):
    max_water = 0
    left_index = 0
    right_index = len(heights) - 1

    while left_index < right_index:
        # Calculate area based on the shortest line.
        current_water = min(heights[left_index], heights[right_index]) * \
                        (right_index - left_index)
        max_water = max(max_water, current_water)

        # Move the pointer of the shorter line.
        if heights[left_index] < heights[right_index]:
            # Moving the left pointer has potential for larger area
            left_index += 1

        else:
            # Moving right pointer has potential to find larger area
            right_index -= 1

    return max_water

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a two-pointer approach where each pointer represents a vertical line. We initialize one pointer at the beginning of the height array and the other at the end. In each iteration of the while loop, we calculate the area, compare it with the maximum area so far, and then move the shorter pointer inward. Since each pointer moves exactly once, and the distance between the pointers decreases by one in each step, the loop executes at most n times, where n is the size of the height array. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm described uses a constant amount of extra space. It only stores a few variables such as the two pointers representing the left and right boundaries and a variable to store the maximum area found so far. The amount of space used does not depend on the input size N, where N is the number of vertical lines. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null height array	Return 0 if the input array is null or empty, as no container can be formed.
Array with only one element	Return 0 if the array has only one element, as a container needs at least two lines.
Array with all elements equal to 0	The algorithm should return 0 as the maximum water that can be contained is zero.
Array with all elements having the same value (non-zero)	The algorithm should correctly calculate the area using the distance between the first and last element multiplied by that value.
Array with a very large number of elements (performance)	The two-pointer approach is O(n) and efficient enough for large arrays; avoid brute force.
Integer overflow when calculating area	Use `long` data type for area calculation to prevent integer overflow if the input values are large.
Array with extremely large height values	Ensure the algorithm still functions correctly and doesn't suffer from numerical instability or unexpected behavior due to large numbers, and it should still return an integer.
Array where the maximum water is formed at the edges.	The algorithm must consider the edges properly when comparing areas and updating pointers.

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 maximum size of the `height` array? Is it small enough to fit comfortably in memory?
Can the values in the `height` array be zero or negative?
If the `height` array is empty or contains only one element, what should the return value be?
If there are multiple pairs of lines that produce the maximum water, is any one of them acceptable?
What is the expected return type (e.g., integer, float) and should I be concerned about potential overflow issues with large heights and widths?

Brute Force Solution

Approach

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

Consider every possible pair of lines from the set of lines you have.
For each pair, determine the shorter line, as this limits the height of the water the container can hold.
Calculate the distance between the two lines you're currently considering. This is the width of the container.
Multiply the height (the shorter line) by the width (the distance between the lines) to get the area of the container formed by that specific pair of lines.
Compare this area to the largest area you've seen so far. If it's bigger, update the largest area.
After checking every possible pair of lines, the largest area you've kept track of will be the solution.

Code Implementation

def max_area_container_brute_force(heights):
    max_area = 0

    # Iterate through all possible pairs of lines
    for first_line_index in range(len(heights)):
        for second_line_index in range(first_line_index + 1, len(heights)):

            # Determine the height of the container
            # formed by the current pair of lines.
            shorter_line = min(heights[first_line_index], heights[second_line_index])

            # Calculate the width of the container
            container_width = second_line_index - first_line_index

            # Calculate the area of the container
            current_area = shorter_line * container_width

            # Keep track of the maximum area found
            if current_area > max_area:
                max_area = current_area

    return max_area

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by examining the outermost pair of vertical lines.
Calculate the amount of water held within the container formed by these lines. This amount is the container's width (distance between the lines) multiplied by its height (the shorter of the two lines).
Now, consider which line to move. Move the shorter line inward. The idea is that moving the shorter line has the potential to increase the height of the container.
Calculate the water contained by the new container (formed by the new line and the previous taller line).
Keep moving the shorter line inwards, continually calculating the water that can be contained, and always remember the largest amount of water we have seen so far.
Repeat the process until the two lines meet. The greatest amount of water we remembered during this process is the answer.

Code Implementation

def max_area(heights):
    max_water = 0
    left_index = 0
    right_index = len(heights) - 1

    while left_index < right_index:
        # Calculate area based on the shortest line.
        current_water = min(heights[left_index], heights[right_index]) * \
                        (right_index - left_index)
        max_water = max(max_water, current_water)

        # Move the pointer of the shorter line.
        if heights[left_index] < heights[right_index]:
            # Moving the left pointer has potential for larger area
            left_index += 1

        else:
            # Moving right pointer has potential to find larger area
            right_index -= 1

    return max_water

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null height array	Return 0 if the input array is null or empty, as no container can be formed.
Array with only one element	Return 0 if the array has only one element, as a container needs at least two lines.
Array with all elements equal to 0	The algorithm should return 0 as the maximum water that can be contained is zero.
Array with all elements having the same value (non-zero)	The algorithm should correctly calculate the area using the distance between the first and last element multiplied by that value.
Array with a very large number of elements (performance)	The two-pointer approach is O(n) and efficient enough for large arrays; avoid brute force.
Integer overflow when calculating area	Use `long` data type for area calculation to prevent integer overflow if the input values are large.
Array with extremely large height values	Ensure the algorithm still functions correctly and doesn't suffer from numerical instability or unexpected behavior due to large numbers, and it should still return an integer.
Array where the maximum water is formed at the edges.	The algorithm must consider the edges properly when comparing areas and updating pointers.