DATA STRUCTURES • ALGORITHMS

Container With Most Water

Given n non-negative integers representing heights of vertical lines, find two lines that together with the x-axis form a container that holds the most water.

Time

O(N)

Space

O(1)

Key Principle 1

Two-pointer strategy

Key Principle 2

Area = (right - left) * min(h[left], h[right])

Key Principle 3

Move the shorter pointer inward

Key Principle 4

Greedy optimization for maximal area

MOST_WATER_LAB
HEIGHTS:
Current Step
Initialize pointers at boundaries.
Playback
Search Stats ⠿
MAX AREA0
CUR AREAN/A
Greedy Logic ⠿
1int l = 0, r = n - 1, maxArea = 0;
2while (l < r) {
3    int area = min(height[l], height[r]) * (r - l);
4    maxArea = max(maxArea, area);
5    if (height[l] < height[r]) l++;
6    else r--;
7}
L
1
2
3
4
5
6
7
R

Loading Lab...