MEDIUM
DATA STRUCTURES AND ALGORITHMS

How to Solve Container With the Most Water

GRAPH THEORYARRAYSSEARCHSORTING
Written By
tom-wagner.png
Tom Wagner
carloswang.png
Carlos Wang

What Is The Container With Most Water Problem?

Container With the Most Water is a coding problem that involves finding the largest possible area that can be formed by two vertical lines on a graph, bound by the height of the shorter line. This problem can be solved using a two-pointer approach, which involves traversing the array from both sides and keeping track of the maximum area found so far.

An Example of the Container With the Most Water Problem

Given n non-negative integers a0, a1, a2, ..., a[n-1], where each represents a point at coordinate (i, a[i]), n vertical lines are drawn such that the two endpoints of the line i is at (i, 0) and (i, ai). Find two lines that, together with the x-axis, form a container that can hold the most amount of water possible.

Example

  • Input: heights = [3, 9, 4, 8, 2, 6, 1]
  • Output: 24

Constraints

  • number of integers n: [2, 10,000]
  • each integer a[i]: [0, 1,000]

Practice the Container With the Most Water Problem With Our AI Interviewer

Start AI Interview

Two Ways to Solve the Container With the Most Water Problem

There are two ways to approach the Container With the Most Water technical interview question. You can either take the brute force or the two pointers approach.

Approach 1: Brute Force

In the context of this problem, the size of the 2D container is determined by multiplying its width by its height. The brute force approach is use nested for loops to calculate all possible containers to find the largest one.

To accomplish this, we can iterate over the heights with an outer loop, and form a container with every other height to its right using an inner loop. Each subarray that we generate this way is a possible container - the container's size will be the lower of the two heights multiplied by the distance between the heights.

We can track the max container size as we go and return the max container size at the end of our iteration.

Container With the Most Water Python, Javascript and Java Solution - Brute Force

def max_water(heights: list[int]) -> int:
    ln = len(heights)
    max_area = 0
    for left_index in range(ln):
        left_height = heights[left_index]
        for right_index in range(left_index + 1, ln):
            right_height = heights[right_index]
            width = right_index - left_index
            height = min(left_height, right_height)
            area = width * height
            max_area = max(area, max_area)
    return max_area
Time / Space Complexity
  • Time complexity: O(n²)
  • Space complexity: O(1). No need for extra space, since we’re just iterating over the matrix.

The nested loops produce O(n²) time complexity.

Approach 2 (Optimal): Two Pointers

Although the brute force approach does not repeat any calculations, it ignores useful information that can help eliminate unnecessary calculations. For example, if a container has sides a[i] and a[j] such that a[i] < a[j], all containers with sides a[i] to a[i+1], ... a[j-1] will have a maximum height of a[i] with a smaller width than j - i, producing less area than the original container. Thus, these possibilities do not need to be considered when we're looking for maximum area.

Instead of trying every combination, we start the 2 pointers at opposite ends (indexes 0 and n-1) to represent the sides of the container. After computing the area using the lower height and distance between the pointers, the options are to increment the left pointer or decrement the right pointer.

Because we want to maximize the water contained, move the pointer with the lower height toward the other pointer. If the heights are equal, we can update either pointer because any potential increase in the next height is limited by one of the equal existing heights. The process is repeated until the pointers meet.

Container With the Most Water Python, JavaScript and Java Solution - Two Pointers

def max_water(heights):
    left_index = 0
    right_index = len(heights) - 1
    max_area = 0
    while left_index < right_index:
        width = right_index - left_index
        left_height = heights[left_index]
        right_height = heights[right_index]
        min_height = min(left_height, right_height)
        area = width * min_height
        max_area = max(area, max_area)
        if left_height <= right_height:
            left_index += 1
        else:
            right_index -= 1
    return max_area

Time / Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Because the left or right pointer is moved toward the other in each iteration until they meet, the list of integers is traversed once.

Watch Mock Interviews Featuring the Container With the Most Water Question

interviewing.io is a mock interview platform, and people in our community routinely share their interview replays to help others get better. In the video below, you can watch people solve Container With the Most Water. The interview is in Python. The interviewer is an anonymous senior engineer from FAANG.
FAANG InterviewPython Interview
Advance this person to the next round?
Thumbs up
Technical Skills:
4/4
Problem Solving Ability:
4/4
Communication Ability:
4/4
Show Transcript

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.