Maximize Water Storage Between Lines

Picture an array of vertical walls at different heights. You pick two walls, fill the space between them with water, and measure how much water fits. Which two walls hold the most? That is the Container With Most Water problem, one of the most popular two-pointer questions asked at Google, Amazon, Yahoo, Uber, and Bloomberg. On Firecode.io it appears as "Maximize Water Storage Between Lines," but the problem is also known as Container With Most Water on other platforms. If you can solve this in O(n) time during an interview, you have demonstrated that you understand the greedy two-pointer technique, a pattern that transfers to dozens of other problems.

TL;DR

Place two pointers at the far ends of the array. Compute the area between them: width * min(height[left], height[right]). Move the pointer at the shorter line inward, because that is the only way the area can potentially increase. Repeat until the pointers meet. This runs in O(n) time and O(1) space.

Why This Problem Matters

Container With Most Water teaches a core principle: when two pointers start at opposite ends of a sorted or structured input, you can eliminate large regions of the search space in a single comparison. The same converging two-pointer pattern appears in Two Sum II, 3Sum, and Valid Palindrome. Getting this problem right shows interviewers that you can reason about greedy choices and prove their correctness, not just code a loop.

Understanding the Problem

Given: An integer array height of size n, where each element represents the height of a vertical line at that index.

Find: Two lines that, together with the x-axis, form a container holding the maximum amount of water.

Return: The maximum area.

The area between two lines at indices left and right is:

area = (right - left) * min(height[left], height[right])

Water can only be filled up to the shorter of the two lines, because it would spill over otherwise. The width is simply the distance between the two indices.

Here is the example input [1, 8, 6, 2, 5, 4, 8, 3, 7]:

With maxArea([1,8,6,2,5,4,8,3,7]), the expected output is 49. The best pair is index 1 (height 8) and index 8 (height 7): width = 7, height = min(8, 7) = 7, area = 49.

Constraints

• Array length is between 2 and 10,000
• Heights are between 0 and 10,000
• Target O(n) time complexity

The Brute Force Trap

The naive solution checks every possible pair of lines. Two nested loops iterate over all n*(n-1)/2 pairs, computing the area for each. For an array of 10,000 elements, that is roughly 50 million operations. It works, but interviewers expect you to spot the redundancy: most of those pairs cannot possibly beat the current best. The two-pointer approach eliminates those pairs without ever computing their area.

Solution Approach: Converging Two Pointers

Start with the widest possible container by placing left at index 0 and right at the last index. This gives maximum width. The only way to find a larger area is to find a pair with a taller minimum height that compensates for the reduced width.

At each step, move the pointer pointing to the shorter line inward. Why? The area is capped by the shorter line. If you moved the taller pointer instead, the width would shrink while the limiting height stays the same or gets worse, so the area can only decrease. Moving the shorter pointer at least gives a chance of discovering a taller line.

This is a greedy choice, and it works because every pair the algorithm skips is guaranteed to have an area no larger than the best one seen so far.

Prefer a different language? Jump to solutions in other languages.

Step-by-Step Walkthrough

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

Step 1: L=0, R=8

The widest pair. Height is limited by the shorter wall (h=1 at index 0).

Area = 8 * 1 = 8. Since height[0] < height[8], move L right.

Step 2: L=1, R=8

Now L points to a tall wall (h=8) and R to another tall wall (h=7).

Area = 7 * 7 = 49. This turns out to be the maximum. Since height[1] > height[8], move R left.

Steps 3 onward: Convergence

Every subsequent pair has smaller width and no taller minimum height. None beats 49.

After the pointers meet, the algorithm returns 49.

Implementation

public class Solution {
  public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
      int width = right - left;
      int currentHeight = Math.min(height[left], height[right]);
      int currentArea = width * currentHeight;
      maxArea = Math.max(maxArea, currentArea);

      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return maxArea;
  }
}

The loop runs until left meets right. Each iteration either increments left or decrements right, so the loop runs at most n-1 times. Every operation inside the loop is O(1).

Why the Greedy Choice Is Correct

This is the part that trips people up in interviews. The claim is: when we skip a pair by moving the shorter pointer, that skipped pair cannot be optimal.

Consider L and R where height[L] < height[R]. We move L to L+1 and skip the pair (L, R-1), (L, R-2), ..., (L, L+1). For any skipped pair (L, j) where j < R:

• Width is j - L, which is strictly less than R - L
• Height is min(height[L], height[j]), which is at most height[L] (the same limiting factor)

So the area (j - L) * min(height[L], height[j]) is at most (R - L) * height[L], which is the area we already computed. No skipped pair can beat the current best.

This argument applies at every step, so the algorithm finds the global maximum.

Complexity Analysis

Time Complexity: O(n)

Each pointer moves at most n-1 positions total. The left pointer only moves right, the right pointer only moves left, and they meet somewhere in the middle. Every step does O(1) work (one comparison, one area calculation, one pointer move). Total: O(n).

Space Complexity: O(1)

The algorithm uses a fixed set of variables (left, right, maxArea, width, currentHeight, currentArea) regardless of input size. No arrays, no hash maps, no recursion.

Edge Cases Worth Testing

Equal Heights at Ends

With [4, 3, 2, 1, 4], the best pair is the two 4s at indices 0 and 4: area = 4 * 4 = 16. When heights are equal, the code moves right-- (the else branch), which is fine because the current pair has already been evaluated.

Minimum Array Size

With [1, 1], there is only one pair. Area = 1 * 1 = 1. The loop runs once, then the pointers meet.

Ascending or Descending Array

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] both give the same answer: 25. The first pair checked is width=9, min(1,10)=1, area=9. But the best is indices 4 and 9: width=5, min(5,10)=5, area=25 (or symmetrically for the descending case). The algorithm finds it because moving the shorter pointer explores inward toward taller lines.

A Zero in the Array

If one of the heights is 0, any container using that line has area 0. The pointer at the 0-height line gets moved immediately, so it never limits the result.

Common Pitfalls

1. Using the sum of heights instead of the minimum: The water level is the shorter line, not the average or sum. Area = width * min(h[L], h[R]).

2. Moving the taller pointer: This is the most common bug. Moving the taller pointer can only decrease the area because the width shrinks and the limiting height stays the same. Always move the shorter one.

3. Off-by-one in width: Width is right - left, not right - left + 1. The lines are at positions L and R, so the gap between them is R - L.

4. Not handling the equal-height case: When height[left] == height[right], you can move either pointer. The else branch in the code moves right, which is correct. Some implementations move both pointers inward on equality, but that is unnecessary and harder to reason about.

Interview Tips

When solving Container With Most Water in an interview:

1. State the brute force first: "Checking all pairs is O(n^2). We can do better with two pointers starting from opposite ends." This sets up the improvement.

2. Explain the greedy choice clearly: "We move the shorter pointer because the area is limited by the shorter line. Moving the taller line can only make things worse." Interviewers often ask why this is correct.

3. Sketch an example: Draw a few bars of different heights, place L and R at the ends, and walk through two or three iterations. Visuals make the algorithm concrete.

4. Know the proof sketch: "Every pair we skip has the same limiting height and strictly smaller width, so its area is no better than what we already recorded." This separates strong candidates from those who memorized the solution.

5. Mention related problems: "This same converging pointer pattern appears in 3Sum, Two Sum II, and Trapping Rain Water." Showing awareness of the problem family demonstrates depth.

Key Takeaways

• The two-pointer technique converts an O(n^2) brute force into O(n) by eliminating pairs that provably cannot be optimal.
• Always move the pointer at the shorter line. The area is limited by the shorter line, so moving the taller one can only decrease the result.
• The greedy proof is straightforward: skipped pairs have the same height constraint and strictly less width, so they cannot beat the current best.
• O(1) space is achievable because the algorithm only needs two index variables and a running maximum.
• The converging two-pointer pattern transfers directly to 3Sum, Two Sum II, Valid Palindrome, and Trapping Rain Water.

Related Problems

Once you are comfortable with Container With Most Water, try these problems that use similar techniques:

• Zero-Sum Triplet Finder (3Sum) - Fix one element and run converging two pointers on the remainder
• Find Pair Indices in Sorted Array (Two Sum II) - The simplest converging two-pointer problem
• Bracket Harmony Check - Not two pointers, but another problem where structure in the input eliminates brute force

These problems and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. The converging two-pointer pattern alone covers a significant chunk of array and string problems you will see at Google, Amazon, and Meta.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def max_area(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0

        while left < right:
            width = right - left
            current_area = min(height[left], height[right]) * width
            max_area = max(max_area, current_area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Python's min and max builtins make the area calculation a single expression. The loop advances one pointer per iteration.

JavaScript

class Solution {
  maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
      const width = right - left;
      const currentHeight = Math.min(height[left], height[right]);
      const currentArea = width * currentHeight;
      maxArea = Math.max(maxArea, currentArea);

      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return maxArea;
  }
}

Math.min and Math.max handle the height and running maximum. The structure mirrors the Java solution exactly.

TypeScript

class Solution {
  maxArea(height: number[]): number {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
      const width = right - left;
      const currentHeight = Math.min(height[left], height[right]);
      const currentArea = width * currentHeight;
      maxArea = Math.max(maxArea, currentArea);

      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return maxArea;
  }
}

Identical to JavaScript with type annotations. The number types are inferred for local variables.

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxArea(std::vector<int> &height) {
    int left = 0;
    int right = height.size() - 1;
    int max_area = 0;

    while (left < right) {
      int width = right - left;
      int current_height = std::min(height[left], height[right]);
      int current_area = width * current_height;
      max_area = std::max(max_area, current_area);

      if (height[left] < height[right]) {
        ++left;
      } else {
        --right;
      }
    }

    return max_area;
  }
};

C++ takes the vector by reference to avoid copying. std::min and std::max from <algorithm> handle the comparisons.

Go

package solution

func (s *Solution) MaxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0

    for left < right {
        width := right - left
        h := 0
        if height[left] < height[right] {
            h = height[left]
            left++
        } else {
            h = height[right]
            right--
        }
        currentArea := width * h
        if currentArea > maxArea {
            maxArea = currentArea
        }
    }

    return maxArea
}

type Solution struct{}

Go lacks a built-in min for integers (before Go 1.21), so the code combines the height selection and pointer movement in a single if-else. The area calculation uses the height captured before the pointer moves.

Scala

class Solution {
  def maxArea(height: Array[Int]): Int = {
    var left = 0
    var right = height.length - 1
    var maxArea = 0

    while (left < right) {
      val width = right - left
      val currentHeight = Math.min(height(left), height(right))
      val currentArea = width * currentHeight
      maxArea = Math.max(maxArea, currentArea)

      if (height(left) < height(right)) {
        left += 1
      } else {
        right -= 1
      }
    }

    maxArea
  }
}

Scala uses var for the mutable pointers and val for per-iteration constants. The final expression maxArea is the return value.

Kotlin

class Solution {
  fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.lastIndex
    var maxArea = 0

    while (left < right) {
      val width = right - left
      val currentHeight = minOf(height[left], height[right])
      val currentArea = width * currentHeight
      maxArea = maxOf(maxArea, currentArea)

      if (height[left] < height[right]) {
        left++
      } else {
        right--
      }
    }

    return maxArea
  }
}

Kotlin's minOf and maxOf are top-level functions, keeping the code concise. height.lastIndex avoids the length - 1 boilerplate.

Swift

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var left = 0
        var right = height.count - 1
        var maxArea = 0

        while left < right {
            let width = right - left
            let currentHeight = min(height[left], height[right])
            let currentArea = width * currentHeight
            maxArea = max(maxArea, currentArea)

            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }

        return maxArea
    }
}

Swift's global min and max functions work on any Comparable type. The while loop does not require parentheses around the condition.

Rust

impl Solution {
    pub fn max_area(&self, height: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = height.len() - 1;
        let mut max_area = 0;

        while left < right {
            let width = (right - left) as i32;
            let current_height = height[left].min(height[right]);
            let current_area = width * current_height;
            max_area = max_area.max(current_area);

            if height[left] < height[right] {
                left += 1;
            } else {
                right -= 1;
            }
        }

        max_area
    }
}

Rust uses method-style .min() and .max() on i32. The width cast from usize to i32 is needed because right - left produces a usize.

C#

public class Solution {
    public int MaxArea(int[] height) {
        int left = 0;
        int right = height.Length - 1;
        int maxArea = 0;

        while (left < right) {
            int width = right - left;
            int currentHeight = Math.Min(height[left], height[right]);
            int currentArea = width * currentHeight;
            maxArea = Math.Max(maxArea, currentArea);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

C# uses Math.Min and Math.Max (capital M). height.Length replaces Java's height.length.

Dart

import 'dart:math';

class Solution {
  int maxArea(List<int> height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
      int width = right - left;
      int currentHeight = min(height[left], height[right]);
      int currentArea = width * currentHeight;
      maxArea = max(maxArea, currentArea);

      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return maxArea;
  }
}

Dart imports min and max from dart:math. The rest of the logic is identical to the Java version.

PHP

<?php

class Solution {
    public function maxArea(array $height): int {
        $left = 0;
        $right = count($height) - 1;
        $maxArea = 0;

        while ($left < $right) {
            $width = $right - $left;
            $currentHeight = min($height[$left], $height[$right]);
            $currentArea = $width * $currentHeight;
            $maxArea = max($maxArea, $currentArea);

            if ($height[$left] < $height[$right]) {
                $left++;
            } else {
                $right--;
            }
        }

        return $maxArea;
    }
}

PHP's global min and max functions handle the comparisons. count($height) gives the array length.

Ruby

class Solution
  def max_area(height)
    left = 0
    right = height.length - 1
    max_area = 0

    while left < right
      width = right - left
      current_height = [height[left], height[right]].min
      current_area = width * current_height
      max_area = [max_area, current_area].max

      if height[left] < height[right]
        left += 1
      else
        right -= 1
      end
    end

    max_area
  end
end

Ruby uses [a, b].min and [a, b].max for comparisons. The method implicitly returns the last expression.