Container With Most Water

Q: What is the best time complexity for Container With Most Water?

Optimal (two pointers) runs in O(n) time and O(1) extra space. Each step moves one pointer, so there are n - 1 steps.

Q: Which pattern does Container With Most Water use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Trapping Rain Water.

Q: Is there a brute force solution for Container With Most Water?

Yes. Brute force takes O(n²) time and O(1) space. Try every pair of lines, compute the water each pair holds, and keep the maximum.

Q: Which edge cases should I test for Container With Most Water?

Exactly two lines; Lines of height 0, which hold no water at all; All lines the same height: the two ends win; The best pair is two tall lines close together, not the widest pair.

Medium Arrays & Hashing Two Pointer Original on LeetCode

Reported atMicrosoft Goldman Sachs

Container With Most Water is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an array height of length n. Picture n vertical lines standing on the x-axis: line i sits at position i and is height[i] units tall.

Choose two of the lines. Together with the x-axis they form an open container, and the amount of water it holds is the shorter line’s height times the distance between the two lines. Return the largest amount of water any pair can hold. The container cannot be tilted.

Examples

Example 1

Input: height = [2, 7, 4, 1, 6, 3]
Output: 18
Why: Walls at indices 1 and 4 have heights 7 and 6, they are 3 apart, so the water is min(7, 6) * 3 = 18.

Example 2

Input: height = [5, 5]
Output: 5
Why: The only pair is 1 apart with height 5.

Example 3

Input: height = [1, 3, 2, 5, 2, 4, 1]
Output: 12
Why: Indices 1 and 5 give min(3, 4) * 4 = 12, which beats every other pair.

Constraints

2 <= height.length <= 10^5
0 <= height[i] <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Optimal (two pointers)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)n(n - 1) / 2 pairs, each checked in O(1).

SpaceO(1)Only the running best.

Try every pair of lines, compute the water each pair holds, and keep the maximum.

Loop i from 0 to n - 1 and j from i + 1 to n - 1.
Compute min(height[i], height[j]) * (j - i).
Keep the largest value.

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

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        best = 0
        for i in range(n):
            for j in range(i + 1, n):
                best = max(best, min(height[i], height[j]) * (j - i))
        return best

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int water = min(height[i], height[j]) * (j - i);
                best = max(best, water);
            }
        }
        return best;
    }
};

function maxArea(height) {
    let best = 0;
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            const water = Math.min(height[i], height[j]) * (j - i);
            best = Math.max(best, water);
        }
    }
    return best;
}

2Optimal (two pointers)

TimeO(n)Each step moves one pointer, so there are n - 1 steps.

SpaceO(1)Two pointers and the running best.

Put one pointer at each end. The shorter of the two lines limits the water. Any other pair that keeps this shorter line is narrower and still capped by it, so it can never do better: drop the shorter line by moving its pointer inward. Repeat until the pointers meet.

Set l = 0, r = n - 1, best = 0.
While l < r: best = max(best, min(height[l], height[r]) * (r - l)).
If height[l] < height[r], move l right; otherwise move r left.
Return best.

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

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            best = max(best, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = (int)height.size() - 1;
        int best = 0;
        while (l < r) {
            int water = min(height[l], height[r]) * (r - l);
            best = max(best, water);
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return best;
    }
};

function maxArea(height) {
    let l = 0, r = height.length - 1;
    let best = 0;
    while (l < r) {
        const water = Math.min(height[l], height[r]) * (r - l);
        best = Math.max(best, water);
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return best;
}

Edge cases to test

Exactly two lines
Lines of height 0, which hold no water at all
All lines the same height: the two ends win
The best pair is two tall lines close together, not the widest pair

Hints

Hint 1

The water between lines i and j is min(height[i], height[j]) * (j - i). What does checking every pair cost?

Hint 2

Start with the widest pair: the two ends. Which end can never be part of a better answer?

Hint 3

Moving the taller line inward can only lower the width without raising the limiting height. Always move the shorter one.

FAQ

What is the best time complexity for Container With Most Water?

Optimal (two pointers) runs in O(n) time and O(1) extra space. Each step moves one pointer, so there are n - 1 steps.

Which pattern does Container With Most Water use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Trapping Rain Water.

Is there a brute force solution for Container With Most Water?

Yes. Brute force takes O(n²) time and O(1) space. Try every pair of lines, compute the water each pair holds, and keep the maximum.

Which edge cases should I test for Container With Most Water?

Exactly two lines; Lines of height 0, which hold no water at all; All lines the same height: the two ends win; The best pair is two tall lines close together, not the widest pair.