11. Container With Most Water - Explanation

Description

You are given an integer array heights where heights[i] represents the height of the $i^{th}$ bar.

You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Example 1:

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

Output: 36

Explanation: The bars at indices 1 and 7 have heights 7 and 6. The container has width 7 - 1 = 6 and height min(7, 6) = 6, so it can store 6 * 6 = 36 units of water. This is the maximum possible area.

Example 2:

Input: height = [2,2,2]

Output: 4

Constraints:

2 <= height.length <= 100,000
0 <= height[i] <= 10,000

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to try all pairs of bars in the array, compute the water for each pair, and return the maximum water among all pairs. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Can you think of an algorithm that runs in linear time and is commonly used in problems that deal with pairs of numbers? Find a formula to calculate the amount of water when we fix two heights.

Hint 3

We can use the two pointer algorithm. One pointer is at the start and the other at the end. At each step, we calculate the amount of water using the formula (j - i) * min(heights[i], heights[j]). Then, we move the pointer that has the smaller height value. Can you think why we only move the pointer at smaller height?

Hint 4

If heights[i] is smaller, then any future container using index i will have a smaller width, and its height is still at most heights[i]. So it cannot produce a larger area than the current pair. Therefore, we can safely discard the smaller height and move that pointer inward. The same logic applies when heights[j] is smaller.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Understanding how to iterate through and access array elements by index
Two Pointers Technique - Moving pointers from opposite ends of an array to efficiently search for optimal pairs

1. Brute Force

Intuition

We try every possible pair of lines and compute the area they form.
For each pair (i, j), the height of the container is the shorter of the two lines, and the width is the distance between them.
By checking all pairs, we are guaranteed to find the maximum area.

Algorithm

Initialize res = 0 to track the maximum area found.
Use two nested loops:
- Outer loop picks the left line i.
- Inner loop picks the right line j > i.
For each pair (i, j):
- Compute the height as min(heights[i], heights[j]).
- Compute the width as j - i.
- Update res with the maximum of its current value and the new area.
After checking all pairs, return res.

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

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

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

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    maxArea(heights) {
        let res = 0;
        for (let i = 0; i < heights.length; i++) {
            for (let j = i + 1; j < heights.length; j++) {
                res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxArea(int[] heights) {
        int res = 0;
        for (int i = 0; i < heights.Length; i++) {
            for (int j = i + 1; j < heights.Length; j++) {
                res = Math.Max(res, Math.Min(heights[i], heights[j]) * (j - i));
            }
        }
        return res;
    }
}

class Solution {
    fun maxArea(heights: IntArray): Int {
        var res = 0
        for (i in heights.indices) {
            for (j in i + 1 until heights.size) {
                val area = minOf(heights[i], heights[j]) * (j - i)
                res = maxOf(res, area)
            }
        }
        return res
    }
}

class Solution {
    func maxArea(_ heights: [Int]) -> Int {
        var res = 0
        for i in 0..<heights.count {
            for j in (i + 1)..<heights.count {
                res = max(res, min(heights[i], heights[j]) * (j - i))
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_area(heights: Vec<i32>) -> i32 {
        let mut res = 0;
        for i in 0..heights.len() {
            for j in (i + 1)..heights.len() {
                res = res.max(heights[i].min(heights[j]) * (j - i) as i32);
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Two Pointers

Intuition

Using two pointers lets us efficiently search for the maximum area without checking every pair.
We start with the widest container (left at start, right at end).
The height is limited by the shorter line, so to potentially increase the area, we must move the pointer at the shorter line inward.
Moving the taller line never helps because it keeps the height the same but reduces the width.
By always moving the shorter side, we explore all meaningful possibilities.

Algorithm

Initialize two pointers:
- l = 0
- r = len(heights) - 1
Set res = 0 to store the maximum area.
While l < r:
- Compute the current area:
  area = min(heights[l], heights[r]) * (r - l)
- Update res with the maximum area so far.
- Move the pointer at the shorter height:
  - If heights[l] <= heights[r], move l right.
  - Otherwise, move r left.
Return res after the pointers meet.

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        l, r = 0, len(heights) - 1
        res = 0

        while l < r:
            area = min(heights[l], heights[r]) * (r - l)
            res = max(res, area)
            if heights[l] <= heights[r]:
                l += 1
            else:
                r -= 1
        return res

public class Solution {
    public int maxArea(int[] heights) {
        int l = 0;
        int r = heights.length - 1;
        int res = 0;

        while (l < r) {
            int area = Math.min(heights[l], heights[r]) * (r - l);
            res = Math.max(res, area);
            if (heights[l] <= heights[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxArea(vector<int>& heights) {
        int l = 0;
        int r = heights.size() - 1;
        int res = 0;

        while (l < r) {
            int area = min(heights[l], heights[r]) * (r - l);
            res = max(res, area);

            if (heights[l] <= heights[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    maxArea(heights) {
        let l = 0;
        let r = heights.length - 1;
        let res = 0;

        while (l < r) {
            const area = Math.min(heights[l], heights[r]) * (r - l);
            res = Math.max(res, area);
            if (heights[l] <= heights[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxArea(int[] heights) {
        int res = 0;
        int l = 0, r = heights.Length-1;

        while (l < r){
            int area = (Math.Min(heights[l], heights[r])) * (r - l);
            res = Math.Max(area, res);

            if (heights[l] <= heights[r]){
                l++;
            } else{
                r--;
            }
        }
        return res;
    }
}

func maxArea(heights []int) int {
    l, r := 0, len(heights) - 1
    res := 0

    for l < r {
        area := min(heights[l], heights[r]) * (r - l)
        if area > res {
            res = area
        }
        if heights[l] <= heights[r] {
            l++
        } else {
            r--
        }
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun maxArea(heights: IntArray): Int {
        var l = 0
        var r = heights.size - 1
        var res = 0

        while (l < r) {
            val area = minOf(heights[l], heights[r]) * (r - l)
            res = maxOf(res, area)
            if (heights[l] <= heights[r]) {
                l++
            } else {
                r--
            }
        }
        return res
    }
}

class Solution {
    func maxArea(_ heights: [Int]) -> Int {
        var l = 0, r = heights.count - 1
        var res = 0

        while l < r {
            let area = min(heights[l], heights[r]) * (r - l)
            res = max(res, area)
            if heights[l] <= heights[r] {
                l += 1
            } else {
                r -= 1
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_area(heights: Vec<i32>) -> i32 {
        let mut l = 0usize;
        let mut r = heights.len() - 1;
        let mut res = 0;

        while l < r {
            let area = heights[l].min(heights[r]) * (r - l) as i32;
            res = res.max(area);
            if heights[l] <= heights[r] {
                l += 1;
            } else {
                r -= 1;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Moving the Wrong Pointer

The algorithm requires moving the pointer at the shorter height inward. Moving the taller pointer instead never increases the area (since height is limited by the shorter side) and can cause the algorithm to miss the optimal solution.

Confusing This Problem with Trapping Rain Water

Unlike the Trapping Rain Water problem where you need to sum water trapped between bars, this problem finds a single container formed by two lines. Applying the wrong mental model leads to incorrect area calculations.

Off-by-One Errors in Width Calculation

The width between indices l and r is r - l, not r - l + 1. Using the wrong formula overestimates the area by one unit for every pair, leading to incorrect results.