Log inSign up
mediumLeetCodeNot Started

Container With Most Water

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Array:

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: The vertical lines are at index 1 (height 8) and index 8 (height 7). The width is 8 - 1 = 7, and height is min(8, 7) = 7. Area = 7 * 7 = 49.

Example 2 · Two Equal Lines:

Input: height = [1, 1]
Output: 1
Explanation: Width = 1, height = min(1, 1) = 1. Area = 1 * 1 = 1.

Example 3 · Descending Heights:

Input: height = [4, 3, 2, 1, 4]
Output: 16
Explanation: Left index 0 (height 4) and right index 4 (height 4) span width 4. Area = 4 * 4 = 16.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two-pointer technique on opposite ends
  • Greedy elimination strategy
  • Understanding geometric area formulas (width * height)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why moving the shorter boundary is mathematically optimal.
  • Formulate single-pass O(N) two-pointer solutions without nested loops.
  • Eliminate sub-optimal candidate pairs efficiently.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximizing an objective function of the form min(A[i], A[j]) * (j - i).
  • Pair optimization on a 1D array where moving boundaries changes width monotonically.
  • A greedy decision rule exists to eliminate impossible sub-problems.

Algorithmic Decision Tree:

  • When maximizing min(h[l], h[r]) * (r - l): Place pointers at opposite ends and greedily move the pointer pointing to the smaller height inward.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Nested Loops All Pairs

Intuition

Check every possible pair of lines (i, j) and compute the trapped area min(height[i], height[j]) * (j - i).

Algorithm

  1. 1. Initialize maxArea = 0.
  2. 2. For i from 0 to n-1: - For j from i+1 to n-1: - currentArea = min(height[i], height[j]) * (j - i) - maxArea = max(maxArea, currentArea).
  3. 3. Return maxArea.

Brute Force All Pairs Area Comparison

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [2, 7, 3, 6, 4, 8]
Current operationSTEP 1 OF 7
Pair (0, 1): First pair evaluation
Visual state
Values and pointers at this exact step
pointers
S
2
7
3
6
4
8
0
↑ i=0
1
↑ j=1
2
3
4
5
Variables at this step
Left Wall
Idx 0 (2)
Right Wall
Idx 1 (7)
Width
1
Area
2
Max Area
2
Check / comparison
Area = min(2, 7) * (1 - 0) = 2 * 1 = 2.
Decision / next transition
maxArea = 2. Advance j to 2.
Why this step matters

Pair (0, 1): First pair evaluation. Area is 2. Increment j.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxArea(vector<int>& height) {
17 int n = height.size();
18 int maxWater = 0;
19 for (int i = 0; i < n; ++i) {
20 for (int j = i + 1; j < n; ++j) {
21 int h = min(height[i], height[j]);
22 int w = j - i;
23 maxWater = max(maxWater, h * w);
24 }
25 }
26 return maxWater;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
33 cout << "Max Water Area: " << sol.maxArea(height) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Evaluates all N*(N-1)/2 pairs in nested loops, resulting in O(N2) runtime.
  • Space complexity: O(1) — Only uses a single integer variable for tracking maximum area. Auxiliary space is O(1).

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Two Pointers with Fast Inner Leap (Pruned)

Intuition

Use two pointers, and when shifting the smaller height, jump past all consecutive shorter heights.

Algorithm

  1. 1. Initialize left = 0, right = height.length - 1, maxWater = 0.
  2. 2. While left < right: - minH = min(height[left], height[right]) - maxWater = max(maxWater, minH * (right - left)) - If height[left] <= height[right], advance left while left < right and height[left] <= minH. - Else, decrement right while left < right and height[right] <= minH.
  3. 3. Return maxWater.

Two Pointers with Fast Inner Leap Pruning

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 7, 3, 6, 4, 8]
Current operationSTEP 1 OF 6
Step 1 — Baseline Evaluation: Width is 5
Visual state
Values and pointers at this exact step
pointers
S
2
7
3
6
4
8
0
↑ L=0 (h=2)
1
2
3
4
5
↑ R=5 (h=8)
Variables at this step
L
0
R
5
Width
5
Current Area
10
Max Area
10
Prune
Skip left <= 2
Check / comparison
w = 5, h = min(2, 8) = 2. Area = 2 * 5 = 10.
Decision / next transition
Left wall 2 is limiting. Prune all lines <= 2 on left.
Why this step matters

Step 1 — Baseline Evaluation: Width is 5. Water is limited by height 2. Area is 10. Left wall is the bottleneck.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxArea(vector<int>& height) {
17 int left = 0, right = height.size() - 1;
18 int maxWater = 0;
19 while (left < right) {
20 int minH = min(height[left], height[right]);
21 maxWater = max(maxWater, minH * (right - left));
22 while (left < right && height[left] <= minH) left++;
23 while (left < right && height[right] <= minH) right--;
24 }
25 return maxWater;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
32 cout << "Max Water Area: " << sol.maxArea(height) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Both pointers only move inward, touching each element at most once. Total time is O(N) with faster practical execution.
  • Space complexity: O(1) — Requires only integer pointers. Auxiliary space is O(1).

3. Shrinking Two Pointers (Standard Optimal)

Intuition

Start with the widest container (left = 0, right = n - 1) and greedily move the pointer pointing to the shorter line inward.

Algorithm

  1. 1. Initialize left = 0, right = height.length - 1, maxWater = 0.
  2. 2. While left < right: - currentArea = min(height[left], height[right]) * (right - left) - maxWater = max(maxWater, currentArea) - If height[left] < height[right], left++ - Else right--.
  3. 3. Return maxWater.

Two-Pointer Inward Shrink Execution Trace

2 of 2 questions left today
Step 1 / 11
Trace timeline9% explored
InputINPUT nums = [2, 7, 3, 6, 4, 8]
Current operationSTEP 1 OF 11
Phase 1 — Initial Widest Span: Left pointer starts at index 0 (height 2) and right pointer at index 5 (height 8)
Visual state
Values and pointers at this exact step
pointers
S
2
7
3
6
4
8
0
↑ L (Left Wall)
1
2
3
4
5
↑ R (Right Wall)
Variables at this step
L Pointer
Idx 0 (h=2)
R Pointer
Idx 5 (h=8)
Current Width
5
Limiting Wall
Left (2)
Current Area
10
Max Area
10
Check / comparison
width = 5 - 0 = 5. Effective height = min(2, 8) = 2. Area = 2 × 5 = 10.
Decision / next transition
Record initial baseline area = 10. Left wall (2) is shorter than right wall (8).
Why this step matters

Phase 1 — Initial Widest Span: Left pointer starts at index 0 (height 2) and right pointer at index 5 (height 8). Width is 5. Water is limited by the shorter wall at index 0 (height 2), giving an initial trapped volume of 2 × 5 = 10 units.

Step 1 / 11
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxArea(vector<int>& height) {
17 int left = 0, right = height.size() - 1;
18 int maxWater = 0;
19 while (left < right) {
20 int h = min(height[left], height[right]);
21 int w = right - left;
22 maxWater = max(maxWater, h * w);
23 if (height[left] < height[right]) left++;
24 else right--;
25 }
26 return maxWater;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
33 cout << "Max Water Area: " << sol.maxArea(height) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — In each iteration, the distance (right - left) decreases by 1. The loop runs exactly N-1 times, taking O(N) linear time.
  • Space complexity: O(1) — Requires only two pointer variables and a max tracker. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Nested Loops All PairsO(N^2)O(1)Check every possible pair of lines (i, j) and compute the trapped area min(height[i], height[j]) * (j - i).Repeated redundant scans over the input.
2.Approach 2: Two Pointers with Fast Inner Leap (Pruned)O(N)O(1)Use two pointers, and when shifting the smaller height, jump past all consecutive shorter heights.Auxiliary memory allocation or sorting step.
3.Approach 3: Shrinking Two Pointers (Standard Optimal)OptimalO(N)O(1)Start with the widest container (left = 0, right = n - 1) and greedily move the pointer pointing to the shorter line inward.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Minimum Size Array (n = 2) — Input height = [4, 6], Expected 4 — With only two lines, width is 1 and area is strictly min(4, 6) * 1 = 4.
  • Uniform Flat Heights [5, 5, 5, 5] — Input height = [5, 5, 5, 5], Expected 15 — Outermost pair spanning width 3 achieves maximum capacity 5 * 3 = 15.
  • Strictly Decreasing Heights [10, 8, 6, 4, 2] — Input height = [10, 8, 6, 4, 2], Expected 12 — Left wall starts high but right side collapses; optimal pair is formed at index 0 and 2 (6 * 2 = 12).
  • Tall Boundary Pillars with Inner Chasm [100, 1, 1, 100] — Input height = [100, 1, 1, 100], Expected 300 — Outer pillars trap 100 * 3 = 300 regardless of low internal walls.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Container With Most Water?

2.Why is the brute force approach suboptimal for large inputs in Container With Most Water?

3.Which data structure or technique enables the optimal solution for Container With Most Water?

Back to DSA Sheet