Container With Most Water

Container With Most Water is a classic two-pointer question. It looks like a geometry puzzle. But it is really about a smart way to move two pointers. The interviewer wants to see if you can prove why moving the shorter side is always the right choice.

🎯 The Problem

You get an array of heights. You have to find the two lines that hold the most water.

• Each number is the height of a vertical line.
• Two lines and the ground form a container.
• The water is the area of the rectangle between the two lines.
• The width is the distance between the lines.
• The height is the shorter of the two lines, because water spills over the shorter wall.
• So area is width times the shorter height.

For heights [1, 8, 6, 2, 5, 4, 8, 3, 7], the best pair is the 8 at index 1 and the 7 at index 8. The width is 8 - 1 = 7. The shorter height is 7. So the area is 7 * 7 = 49.

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

Explanation: lines at index 1 (height 8) and index 8 (height 7).
             width = 7, shorter height = 7, area = 7 * 7 = 49.

Here is the picture. The tall lines are the walls and the gap between two walls holds the water.

🐢 Approach 1: Try Every Pair (Brute Force)

The idea in one line: check every possible pair of lines and keep the biggest area.

The idea:

• Pick a left line. Pick a right line.
• Find the area between them.
• Keep the biggest area you have seen.

How it works:

• Two nested loops walk over the array.
• For each pair, compute width times the shorter height.

Why it is weak:

• Two nested loops over n lines means about n times n pairs.
• Time is O(n²). On a long array this is slow.

Here is the brute-force code for that idea:

def max_area(height):
    best = 0
    for left in range(len(height)):
        for right in range(left + 1, len(height)):
            width = right - left
            water = width * min(height[left], height[right])
            best = max(best, water)
    return best

⚡ Approach 2: Two Pointers (Best)

The idea in one line: start wide, then always close in the shorter wall.

The idea:

• A pointer is a variable holding a position in the array.
• Put one pointer at the first line and one at the last line.
• At the start the lines are as far apart as possible, so the width is largest.

How it works:

• Compute the area for the two current lines. Save it if it is the biggest.
• Then move one pointer inward. Always move the one on the shorter wall.
• Keep going until the two pointers meet.

Why moving the shorter wall is safe:

• The area is capped by the shorter wall.
• Moving the taller wall in keeps the same short cap but shrinks the width. The area can only get worse.
• Moving the shorter wall in gives a chance at a taller wall. The area might rise.

Why it is fast:

• Each pointer moves inward and never goes back.
• Each line is touched once. Time is O(n), space is O(1).

Here is the dry-run for the first few steps on our example.

Steps to Solve

1. Put a left pointer at the first line and a right pointer at the last line.
2. Set the best area to zero.
3. While left is before right, find the width and the shorter height, then compute the area.
4. Update the best area if this area is bigger.
5. Move the pointer that points to the shorter line one step inward.
6. Stop when the pointers meet. Return the best area.

#include <stdio.h>

int maxArea(int height[], int n) {
    int left = 0;
    int right = n - 1;
    int best = 0;
    while (left < right) {
        int h = height[left] < height[right] ? height[left] : height[right]; // shorter wall
        int width = right - left;
        int area = h * width;
        if (area > best) best = area;          // keep the biggest
        if (height[left] < height[right]) {
            left++;                            // move the shorter side
        } else {
            right--;
        }
    }
    return best;
}

int main(void) {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    printf("%d\n", maxArea(height, 9));
    return 0;
}

49

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    int best = 0;
    while (left < right) {
        int h = min(height[left], height[right]);   // shorter wall
        int width = right - left;
        best = max(best, h * width);                // keep the biggest
        if (height[left] < height[right]) {
            left++;                                 // move the shorter side
        } else {
            right--;
        }
    }
    return best;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << maxArea(height) << endl;
    return 0;
}

49

public class MaxWater {
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);  // shorter wall
            int width = right - left;
            best = Math.max(best, h * width);               // keep the biggest
            if (height[left] < height[right]) {
                left++;                                     // move the shorter side
            } else {
                right--;
            }
        }
        return best;
    }

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

49

def max_area(height):
    left = 0                       # pointer at the first line
    right = len(height) - 1        # pointer at the last line
    best = 0
    while left < right:
        h = min(height[left], height[right])   # shorter wall limits the water
        width = right - left
        best = max(best, h * width)            # keep the biggest area
        if height[left] < height[right]:
            left += 1              # move the shorter side inward
        else:
            right -= 1
    return best


height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(height))

49

function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]); // shorter wall
    const width = right - left;
    best = Math.max(best, h * width);                // keep the biggest
    if (height[left] < height[right]) {
      left++;                                        // move the shorter side
    } else {
      right--;
    }
  }
  return best;
}

const height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(height));

49

Let us walk through the Python version line by line. The key is which pointer moves.

left = 0 and right = len(height) - 1 set the two pointers at the far ends. The width starts at its largest. We try the widest container first.

best = 0 holds the biggest area we have found so far.

while left < right: keeps going until the pointers meet. Once they touch, there is no container left to check.

h = min(height[left], height[right]) picks the shorter of the two walls. Water spills over the shorter wall. So the shorter wall sets the height of the container.

width = right - left is the distance between the two lines. best = max(best, h * width) computes the area and keeps it if it beats the current best.

if height[left] < height[right]: left += 1 moves the left pointer when the left wall is shorter. else: right -= 1 moves the right pointer otherwise. We always move the shorter wall. Moving the taller wall could never raise the area, because the short wall would still cap it and the width would shrink. So moving the shorter wall is the only move with a chance to improve.

⏱️ Time and Space Complexity

The brute force checks every pair, so it is O(n²) time. The two-pointer version moves each pointer inward and never goes back. So it touches each line once. That makes it O(n) time and O(1) space. We trade a clever proof for a big speed win.

🧩 Key Takeaways

• ✅ The water height is set by the shorter of the two walls, not the taller one.
• ✅ Start the two pointers at the far ends so the width starts at its largest.
• ✅ Always move the pointer on the shorter wall inward.
• ✅ Moving the taller wall can never raise the area, so it is never the right move.
• ✅ The two-pointer walk runs in O(n) time with O(1) extra memory.

🚀 What’s Next?

• Trapping Rain Water
• 3Sum