Skip to main content
Ace Hired
All coding problems

Container With Most Water

Mediumtwo pointersTwo pointers (converging from both ends)two-pointersarraysgreedy

Maintained by Vikas D, software engineer

Picture a row of upright sticks standing on a number line. The stick at position i rises to height[i]. If you choose any two sticks, water can sit in the rectangle they bound. The width of that rectangle is the gap between the two positions, and the depth is limited by the shorter of the two sticks, because anything taller would simply spill over the lower side.

Your task is to try every possible pairing in spirit and report the single largest area. The area for a pair at indices i and j is (j - i) multiplied by the smaller of height[i] and height[j].

The container has straight vertical walls and a flat floor, so you cannot tilt it to scoop more. Only the two chosen sticks and the ground beneath them matter; sticks in between are ignored and do not block the water.

Examples

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

The stick of height 8 at index 1 and the stick of height 7 at index 8 are 7 apart. Depth is capped at the shorter wall, 7, so the area is 7 * 7 = 49. No other pair beats this.

Input: height = [1, 1]
Output: 1

Only one pair exists. Width 1 times the shorter height 1 gives 1.

Input: height = [4, 3, 2, 1, 4]
Output: 16

The two 4s sit at the far ends, 4 apart. The shorter wall is 4, so 4 * 4 = 16, the best you can do here.

Constraints

  • n == height.length and n >= 2
  • 0 <= height[i] <= 10^4
  • The container must stay upright; tilting is not allowed

Visible test cases

  • maxWater([1,8,6,2,5,4,8,3,7]) == 49
  • maxWater([1,1]) == 1
  • maxWater([4,3,2,1,4]) == 16
  • maxWater([1,2,1]) == 2
  • maxWater([2,3,4,5,18,17,6]) == 17
  • maxWater([1,8,6,2,5,4,8,25,7]) == 49

Hints

Hint 1

The area of any pair depends on two things that pull against each other: a wider gap raises the width, but the depth is always pinned to whichever wall is shorter.

Hint 2

Start with the widest possible gap, one pointer at each end, then ask which move could ever improve things.

Hint 3

Moving the pointer at the taller wall inward can only shrink the width while keeping the same height cap, so it can never help. Always advance the pointer sitting at the shorter wall.

Loading the editor...

Approaches

Brute force over all pairs

Time O(n^2) · Space O(1)

Compute the area for every pair of indices and keep the maximum. Correct but slow because it re-examines pairs that cannot win.

  1. Loop i from 0 to n - 2.
  2. For each i, loop j from i + 1 to n - 1.
  3. Compute (j - i) * min(height[i], height[j]).
  4. Track the largest value seen and return it.

Two pointers from both ends

Time O(n) · Space O(1)

Begin with the widest container and shrink it intelligently. The depth is set by the shorter wall, so abandoning the taller wall can never recover the lost width. Move the shorter wall inward each step, hoping to find a taller one.

  1. Set left to 0 and right to n - 1, and best to 0.
  2. While left < right, compute the area as (right - left) * min(height[left], height[right]) and update best.
  3. If the left wall is shorter than the right wall, increment left; otherwise decrement right.
  4. Stop when the pointers meet and return best.

Common mistakes

  • Using the taller wall for depth. The water level is always capped by the shorter of the two walls, never the taller one.
  • Moving the wrong pointer. Advancing the taller wall throws away width for no gain in height; always move the shorter wall.
  • Computing width as an absolute index difference when it does not need to be: with left always less than right, right - left is already positive, but flipping the subtraction order silently produces negatives.
  • Multiplying the two heights together or summing them instead of taking min(height[left], height[right]) as the limiting depth.
  • Off-by-one on the loop bound, for example stopping while left <= right and computing a zero-width area when the pointers coincide.

Follow-up variations

  • What if you must report the actual pair of indices, not just the maximum area? Track the best indices alongside the running maximum.
  • How would the answer change if the container could be tilted, so the floor need not be level?
  • Compare this with trapping rain water, where you sum the water held above every bar instead of choosing a single best pair. Why does that problem need a different technique?
  • Can you prove formally that the two-pointer sweep never skips the optimal pair?

Recommended problems

Build the rest of your prep