Maximum Water Trapped Between Two Vertical Lines

Medium20–25 min

Topics

ArrayTwo PointerGreedy

Companies

AmazonGoogleMicrosoftAdobe

Given an array height where height[i] is the height of a vertical line standing at index i, pick two lines that, together with the x-axis, form a container. Return the maximum amount of water that container can hold — min(height[i], height[j]) × (j - i) for the pair you pick. Checking every pair works but wastes time re-deriving what a single pass can rule out: since water level is always capped by the shorter of the two chosen lines, a two-pointer sweep that always advances the shorter side finds the answer in O(n).

Test Case 1:

Input:height = [3, 9, 2, 6, 1, 8]

Output:32

Explanation:The lines at index 1 (height 9) and index 5 (height 8) form the best pair — width 4 times the shorter height 8.

Test Case 2:

Input:height = [4, 4]

Output:4

Explanation:Only two lines exist, so they must form the container.

Test Case 3:

Input:height = [1, 1, 1, 1, 1, 1]

Output:5

Explanation:Every line is equally short, so the water depth is capped at 1 everywhere — the widest possible span wins.

Constraints

◆2 ≤ height.length ≤ 10⁵
◆0 ≤ height[i] ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

height (comma-separated) — 2-12 non-negative integers

1	class Solution {
2	public int maxWaterBetweenLines(int[] height) {
3	int left = 0, right = height.length - 1;
4	int maxArea = 0;
5	while (left < right) {
6	int width = right - left;
7	int shorter = Math.min(height[left], height[right]);
8	int area = shorter * width;
9	maxArea = Math.max(maxArea, area);
10	if (height[left] < height[right]) {
11	left++;
12	} else {
13	right--;
14	}
15	}
16	return maxArea;
17	}
18	}
19

↑left

↑right

Variables

left0

right5

maxArea0

INITIALIZE

Set left and right at the two ends of the array, and maxArea to 0 — this is the widest container we could try.

Step 1 / 17

Approach & Solutions

Brute Force

Brute

Try every pair of lines (i, j) with two nested loops. For each pair, compute min(height[i], height[j]) * (j - i) and keep the largest value seen. Correct, but it revisits pairs that a smarter sweep can rule out without ever computing them.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int maxWaterBetweenLines(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}

Optimal — Two Pointers

Optimal

Start with left at index 0 and right at the last index — the widest possible container. At each step, the water level is capped by the shorter of the two lines, so keeping the shorter one and shrinking the width can never help. Move the pointer at the shorter line inward, hoping to find something taller, and track the best area seen along the way.

TimeO(n)