Skip to main content
Talentd

Container With Most Water - Solution & Explanation

MediumArrayTwo PointersGreedy25 min readAsked at: Amazon, Microsoft, Apple +55
Practice this problem

Problem Statement

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.

 

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 <= 105
  • 0 <= height[i] <= 104

Approach Overview

Problem Overview: You get an array height where each value represents the height of a vertical line. Pick two lines that, together with the x-axis, form a container holding the maximum possible water. The container area is determined by the shorter line and the distance between the two indices.

Approach 1: Brute Force (O(n2) time, O(1) space)

The straightforward approach checks every pair of lines. For each pair (i, j), compute the container area using min(height[i], height[j]) * (j - i). Iterate with two nested loops and keep track of the maximum area seen so far. This works because it evaluates all possible containers, guaranteeing the correct result. The downside is the quadratic runtime since there are n(n-1)/2 pairs to examine. This approach mainly helps build intuition for the problem before applying optimizations with techniques like two pointers.

Approach 2: Two Pointers Technique (O(n) time, O(1) space)

The optimal solution uses two pointers starting at opposite ends of the array. One pointer begins at index 0 and the other at n-1. At each step, compute the current area using the width between the pointers and the smaller height. The key insight: the container height is limited by the shorter line, so moving the taller pointer cannot increase the area. Move the pointer pointing to the shorter line inward and recompute the area. This greedy decision removes impossible candidates while still exploring all potentially better containers.

This method works because reducing width is unavoidable when moving pointers, so the only chance to increase area is by finding a taller boundary. By always discarding the shorter wall, the algorithm systematically searches for a better height while keeping the widest possible distance early in the process. The result is a single linear scan of the array using the classic array traversal pattern combined with a greedy elimination strategy.

Recommended for interviews: Interviewers expect the Two Pointers solution. The brute force method shows you understand how the area formula works and can reason about all possibilities. The optimized approach demonstrates pattern recognition and algorithmic efficiency by reducing the search from O(n2) to O(n). Many array optimization problems follow the same pattern of shrinking the search space from both ends.

Approach 1: Approach 1: Two Pointers Technique

The two pointers approach efficiently searches for the maximum area by starting with the widest possible container and gradually narrowing it:

  1. Initialize two pointers, one at the beginning (left) and one at the end (right) of the array.
  2. Calculate the area using the current height at left and right pointers, and update the maximum area when a larger one is found.
  3. Move the pointer pointing to the shorter line inward, as this might lead to a taller container edge and potentially a larger area.
  4. Continue this process until the two pointers meet.

This approach works due to the observation that the area is limited by the shorter line, so the only way to get a larger area is to find a taller line.

This C implementation defines a function maxArea which takes an array of heights and iteratively calculates the maximum water that can be contained using a two-pointer approach. The output is printed after calling the function.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array.
Space Complexity: O(1) as only a few extra variables are used.

Try this approach in the editor ā†’

Approach 2: Approach 2: Brute Force

Although not optimal for large inputs, the brute force approach explores every possible pair of lines to find the maximum container area:

  1. Iterate through each line starting from the first.
  2. For every line, consider all subsequent lines as a potential pair to form a container.
  3. Calculate the area for each pair, and keep track of the maximum area encountered.
  4. This method ensures all possible pairs are considered, leading to the correct result.

However, the complexity of this approach makes it unsuitable for large datasets due to its quadratic time complexity.

This brute force C implementation explores every pair of lines to find the maximum container area by calculating the area for all possible pairs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of elements as each pair is checked.
Space Complexity: O(1) due to a linear amount of extra space.

Try this approach in the editor ā†’

Approach 3: 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.

Next, we use a variable ans to record the maximum capacity of the container, initially set to 0.

Then, we start a loop. In each iteration, we calculate the current capacity of the container, i.e., min(height[l], height[r]) times (r - l), and compare it with ans, assigning the larger value to ans. Then, we compare the values of height[l] and height[r]. If height[l] < height[r], moving the r pointer will not improve the result because the height of the container is determined by the shorter vertical line, so we move the l pointer. Otherwise, we move the r pointer.

After the iteration, we return ans.

The time complexity is O(n), where n is the length of the array height. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

C

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Two Pointers Technique

Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array.
Space Complexity: O(1) as only a few extra variables are used.

Approach 2: Brute Force

Time Complexity: O(n^2), where n is the number of elements as each pair is checked.
Space Complexity: O(1) due to a linear amount of extra space.

Two Pointersā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(nĀ²)O(1)Useful for understanding the area calculation and verifying logic on small inputs
Two Pointers TechniqueO(n)O(1)Optimal solution for large arrays; standard interview approach for this problem

Video Solution

Container with Most Water - Leetcode 11 - Python ā€¢ NeetCode ā€¢ 554,880 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Container With Most Water easy or hard?
Container With Most Water is classified as a Medium problem. The brute force solution is straightforward, but recognizing the two-pointer optimization requires understanding how to eliminate unnecessary pairs while preserving the possibility of finding a larger area.
Container With Most Water Python/Java solution
Python and Java implementations typically follow the same two-pointer logic: initialize left and right indices, compute area using min(height[left], height[right]), update the maximum, and move the pointer with the smaller height. The loop continues until the pointers meet, achieving O(n) runtime.
How to solve Container With Most Water in O(n)?
Place two pointers at the leftmost and rightmost indices of the height array. Calculate the area using the shorter height and the width between pointers. Move the pointer pointing to the smaller height inward and repeat until the pointers meet. This strategy works because only a taller boundary can increase the possible container height.
What is the best approach for Container With Most Water?
The best approach uses the Two Pointers technique. Start with one pointer at the beginning of the array and another at the end, compute the container area, then move the pointer with the smaller height inward. This greedy rule ensures all useful candidates are considered while scanning the array once, giving O(n) time and O(1) space complexity.
Is Container With Most Water asked at Google/Amazon/Meta?
Container With Most Water is a common interview problem at companies like Google, Amazon, Meta, and Microsoft. It tests recognition of the two-pointer pattern, reasoning about greedy decisions, and the ability to reduce a brute force search space to a linear scan.
What data structure is used in Container With Most Water?
The problem primarily uses an array along with the two pointers technique. No additional data structures such as hash maps or stacks are required. The algorithm operates directly on the array indices while maintaining constant extra memory.
What is the time complexity of Container With Most Water?
The optimal solution runs in O(n) time using the two pointers technique because each pointer moves at most once across the array. The brute force method checks every pair of lines and takes O(n^2) time. Both approaches use O(1) additional space.

Ready to solve this problem?

Practice Container With Most Water with our built-in code editor and test cases.

Practice on FleetCode
Previous

House Robber IV

Next

Maximum Tastiness of Candy Basket