Container With Most Water

Master this topic with zero to advance depth.

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^{th} 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.

Visual Representation

Height: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Index:   0  1  2  3  4  5  6  7  8

    |                   |
    |                   |       |
    |   |               |       |
    |   |       |       |       |
    |   |       |   |   |       |
    |   |       |   |   |   |   |
    |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |
0   1   2   3   4   5   6   7   8
    L                           R  
    (Area = min(8, 7) * (8 - 1) = 7 * 7 = 49)

Medium

Examples

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The max area is between index 1 (height 8) and index 8 (height 7). Area = min(8, 7) * (8 - 1) = 49.

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

To find the maximum water, we can check every possible pair of lines and calculate the volume of water they can hold. The volume is determined by the shorter of the two lines multiplied by the distance between them.

Check every possible pair of lines and calculate the area for each. Keep track of the maximum area found so far.

⏱ O(N^2)💾 O(1)

Detailed Dry Run

Left Index (i)	Right Index (j)	Height[i]	Height[j]	Width (j-i)	Min Height	Area	Max Area
0	1	1	8	1	1	1	1
0	2	1	6	2	1	2	2
0	8	1	7	8	1	8	8
1	2	8	6	1	6	6	8
1	8	8	7	7	7	49	49

java

public class Solution {
    public int maxArea(int[] height) {
        int max = 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);
                max = Math.max(max, area);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
    }
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity leads to TLE for large inputs.

Approach 2

Level II: Greedy (Optimized Two Pointers)

Intuition

We can improve the basic two-pointer approach by skipping heights that are smaller than or equal to the heights we've already processed on either side. This doesn't change the asymptotic O(N) complexity but reduces the number of area calculations in practice.

Start with two pointers. After calculating the area, move the pointer pointing to the shorter bar. Instead of calculating the area at every step, continue moving that pointer as long as the next bar is shorter than the one we just left.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

L=0(1), R=8(7). Area=8. Move L.
L=1(8). Current Max Area = 8.
R=8(7). Area=49. Move R.
R=7(3). H[7] < H[8]. SKIP! Move R to index 6.
R=6(8). Area=40. ...

java

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1, max = 0;
    while (l < r) {
        int h = Math.min(height[l], height[r]);
        max = Math.max(max, h * (r - l));
        while (l < r && height[l] <= h) l++;
        while (l < r && height[r] <= h) r--;
    }
    return max;
}

⚠️ Common Pitfalls & Tips

While this skips some iterations, it is still O(N) in the worst case.

Approach 3

Level III: Optimal (Two Pointers - Collision)

Intuition

The area is limited by the shorter bar. If we move the pointer pointing to the longer bar inward, the width decreases while the height stays limited by the same (or an even shorter) shorter bar, meaning the area can only decrease.

Therefore, the only way to potentially find a larger area is to move the pointer pointing to the shorter bar inward, in hopes of finding a taller bar that compensates for the loss in width.

Start with two pointers at both ends. The area is limited by the shorter line. To potentially find a larger area, we must replace the shorter line by moving that pointer inward.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

L	R	H[L]	H[R]	Width	Current Area	Max Area	Action
0	8	1	7	8	1*8 = 8	8	H[L] < H[R] → L++
1	8	8	7	7	7*7 = 49	49	H[R] < H[L] → R--
1	7	8	3	6	3*6 = 18	49	H[R] < H[L] → R--
1	6	8	8	5	8*5 = 40	49	H[L] = H[R] → L++ or R--

java

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, max = 0;
        while (l < r) {
            max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
    }
}

⚠️ Common Pitfalls & Tips

Always move the pointer with the smaller height. If both are equal, moving either side is fine.

← Previous QuestionContinuous Subarray Sum

Next Question →Two Sum II - Input Array Is Sorted

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.