Skip to main content
CodePeetCodePeet
CodePeet 150

Container With maximium Water

MEDIUMProblemSolveExternal Links

Description

You are given an integer array height of length n. Each element height[i] represents the height of a vertical line drawn at position i along the x-axis. The line extends from coordinate (i, 0) to coordinate (i, height[i]).

Your task is to pick two of these vertical lines so that, together with the x-axis, they form a container that holds the maximum possible amount of water. The amount of water a container can hold is determined by the shorter of the two chosen lines (because water would spill over the shorter side) multiplied by the horizontal distance between the two lines.

Return the maximum amount of water the container can store.

Important: You cannot tilt the container — it must remain upright.

Examples

Example 1

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

Output: 49

Explanation: The two lines chosen are at index 1 (height 8) and index 8 (height 7). The container's height is limited by the shorter line: min(8, 7) = 7. The width between the lines is 8 - 1 = 7. So the area of water held is 7 × 7 = 49. No other pair of lines can form a container that holds more water than this.

Example 2

Input: height = [1, 1]

Output: 1

Explanation: There are only two lines, both with height 1. The container's height is min(1, 1) = 1 and the width is 1 - 0 = 1, giving an area of 1 × 1 = 1.

Example 3

Input: height = [1, 5, 4, 3]

Output: 6

Explanation: Choosing the lines at index 1 (height 5) and index 3 (height 3) gives width = 3 - 1 = 2 and height = min(5, 3) = 3, so the area is 3 × 2 = 6. This is the maximum possible among all pairs.

Constraints

  • n == height.length
  • 2 ≤ n ≤ 10^5
  • 0 ≤ height[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to consider every possible pair of vertical lines and calculate how much water each pair can hold. For any two lines at positions i and j (where j > i), the water they can hold is:

water = min(height[i], height[j]) × (j - i)

The height of the water is capped by the shorter line (since water would overflow over the shorter side), and the width is simply the horizontal distance between the two positions.

Think of it like trying on every pair of bookends on a shelf to see which pair creates the widest, tallest gap. You pick up the first bookend, slide the second one across every other position, measure the space, then move the first bookend and repeat. It is exhaustive but guaranteed to find the best pair.

Step-by-Step Explanation

Let's trace through with height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

Step 1: Fix i = 0 (height 1). We will pair it with every j > 0.

Step 2: Pair (i=0, j=1): water = min(1, 8) × (1-0) = 1 × 1 = 1. max_area = 1.

Step 3: Pair (i=0, j=8): water = min(1, 7) × (8-0) = 1 × 8 = 8. max_area = 8.

  • Even with the widest possible gap, line at index 0 is so short (height 1) that it limits every container to at most height 1.

Step 4: Move to i = 1 (height 8). Pair with j = 2 onward.

Step 5: Pair (i=1, j=2): water = min(8, 6) × (2-1) = 6 × 1 = 6. max_area stays 8.

Step 6: Pair (i=1, j=6): water = min(8, 8) × (6-1) = 8 × 5 = 40. max_area = 40.

Step 7: Pair (i=1, j=8): water = min(8, 7) × (8-1) = 7 × 7 = 49. max_area = 49.

Step 8: Continue checking all remaining pairs (i=2..7 with their j values). None exceed 49.

Result: max_area = 49. We checked all n×(n-1)/2 = 36 pairs to find this answer.

Brute Force — Checking All Pairs — Watch how the brute force method exhaustively evaluates every pair of lines, updating the maximum area whenever a larger container is found.

Algorithm

  1. Initialize max_area = 0
  2. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • Compute water = min(height[i], height[j]) × (j - i)
      • Update max_area = max(max_area, water)
  3. Return max_area

Code

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int maxArea = 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);
                maxArea = max(maxArea, water);
            }
        }
        
        return maxArea;
    }
};
class Solution:
    def maxArea(self, height: list[int]) -> int:
        n = len(height)
        max_area = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                water = min(height[i], height[j]) * (j - i)
                max_area = max(max_area, water)
        
        return max_area
class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int water = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, water);
            }
        }
        
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each iteration the inner loop runs up to n-1 times. The total number of pairs checked is n × (n-1) / 2, which simplifies to O(n²). Each pair evaluation is O(1), so the overall time is O(n²).

Space Complexity: O(1)

We only use a constant number of variables (max_area, i, j, water) regardless of input size. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force evaluates every possible pair of lines, resulting in O(n²) time complexity. With n up to 10^5, that means up to ~5 × 10^9 pair evaluations — far too slow for typical time limits of 1-2 seconds.

The core waste lies in the fact that we check many pairs that we could logically eliminate. For instance, if we already have a container of area 49, there is no point checking pairs where both lines are short or very close together.

The key insight that leads to a better approach: if we start with the widest possible container (leftmost and rightmost lines), we can systematically narrow the search. When we have two lines, the container's area is limited by the shorter line. Moving the taller line inward can only make things worse (we lose width without gaining height). But moving the shorter line inward might find a taller line that more than compensates for the lost width. This greedy elimination lets us solve the problem in a single pass.

Optimal Approach - Two Pointers

Intuition

Instead of checking all pairs, we use two pointers — one starting at the far left and one at the far right of the array. This gives us the widest possible container to start with.

At each step, we compute the area between the two pointer positions. Then we make a greedy decision: move the pointer pointing to the shorter line inward.

Why does this work? Consider the current pair of lines. The water level is limited by the shorter line. If we moved the pointer at the taller line inward, the width would decrease, and the height can only stay the same or get shorter (since the shorter line still constrains us). So the area would definitely not increase — we can safely skip all those pairs.

However, if we move the pointer at the shorter line inward, we might discover a much taller line that creates a bigger container despite the reduced width. We are eliminating pairs that provably cannot beat the current best, which is why this greedy approach finds the global optimum.

Imagine two people standing at opposite ends of a fence made of posts of varying heights. They want to find which two posts can hold the most water between them. They start at the ends (maximum width) and the shorter person steps inward, hoping to find a taller post. The taller person stays put because moving them would only reduce the width without helping the height.

Step-by-Step Explanation

Let's trace through with height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

Step 1: Initialize left = 0, right = 8. Compute area = min(1, 7) × (8 - 0) = 1 × 8 = 8. max_area = 8.

Step 2: height[left]=1 < height[right]=7, so move left pointer inward. left = 1.

Step 3: Compute area = min(8, 7) × (8 - 1) = 7 × 7 = 49. max_area = 49.

Step 4: height[left]=8 > height[right]=7, so move right pointer inward. right = 7.

Step 5: Compute area = min(8, 3) × (7 - 1) = 3 × 6 = 18. 18 < 49, max_area stays 49.

Step 6: height[left]=8 > height[right]=3, so move right pointer inward. right = 6.

Step 7: Compute area = min(8, 8) × (6 - 1) = 8 × 5 = 40. 40 < 49, max_area stays 49.

Step 8: height[left]=8 == height[right]=8, so we move right pointer inward. right = 5.

Step 9: Compute area = min(8, 4) × (5 - 1) = 4 × 4 = 16. 16 < 49, max_area stays 49.

Step 10: height[left]=8 > height[right]=4, so move right pointer inward. right = 4.

Step 11: Compute area = min(8, 5) × (4 - 1) = 5 × 3 = 15. 15 < 49, max_area stays 49.

Step 12: height[left]=8 > height[right]=5, so move right pointer inward. right = 3.

Step 13: Compute area = min(8, 2) × (3 - 1) = 2 × 2 = 4. 4 < 49, max_area stays 49.

Step 14: height[left]=8 > height[right]=2, so move right pointer inward. right = 2.

Step 15: Compute area = min(8, 6) × (2 - 1) = 6 × 1 = 6. 6 < 49, max_area stays 49.

Step 16: height[left]=8 > height[right]=6, so move right pointer inward. right = 1. Now left == right, so we stop.

Result: max_area = 49. Found in just 8 iterations instead of 36 pairs!

Two Pointers — Converging From Both Ends — Watch how two pointers start at opposite ends of the array and converge inward, always moving the pointer at the shorter line to maximize the chance of finding a taller wall.

Algorithm

  1. Initialize two pointers: left = 0 and right = n - 1
  2. Initialize max_area = 0
  3. While left < right:
    • Compute area = min(height[left], height[right]) × (right - left)
    • Update max_area = max(max_area, area)
    • If height[left] < height[right]: increment left by 1
    • Else: decrement right by 1
  4. Return max_area

Code

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
        
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
};
class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0
        
        while left < right:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)
            
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(n)

The two pointers start at opposite ends and move toward each other. Each iteration moves exactly one pointer one step inward. Since the total distance between the pointers is n-1, the loop runs at most n-1 times. Each iteration does O(1) work (one comparison, one multiplication, one max update), giving O(n) total.

Space Complexity: O(1)

We only use three variables (left, right, max_area) plus a temporary area variable. No additional data structures are allocated, so space usage is constant regardless of input size.