Faangprep Logo
LoginRegister
Browse Curriculum
FAANGPrep Sprint
Medium

Container With Most Water

Find two lines that together with the x-axis form a container, such that the container contains the most water.
10 min read
Solve on LeetCode
Examples
Input:height = [1,8,6,2,5,4,8,3,7]
Output:49
Explain:

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

The Problem

You are given an array height where height[i] represents the height of a vertical line. Find two lines that, together with the x-axis, form a container that holds the most water.

Goal: Maximize Area = width * min(height[left], height[right]).

Visualizing the Problem

Step 1 / 1

Initializing...

1x

The container is formed by two vertical lines. The water level (blue) is limited by the shorter line.

Attempt 1: Brute Force

The naive solution is to simply check every pair of lines and calculate the area.

  • Check line 0 with line 1, then line 0 with line 2...
  • Then line 1 with line 2, line 1 with line 3...

Why it fails: This requires nested loops, resulting in O(n^2) time complexity. For a large input, this will time out.

The Intuition: Process of Elimination

Start Wide, Then Eliminate.

  1. Start Max Width: The widest possible container is bounded by the first and last line. Let's start there.
  2. The Decision: We want to find a higher line to potentially get more area. But we can only move one pointer at a time.
    • If height[left] < height[right], the left line is the bottleneck. Moving the right pointer in would only decrease width, and height is still limited by left. We must move left to hope for a taller line.
    • Similarly, if right is shorter, we must discard it and move right inward.

Algorithm Strategy

  1. Start with pointers at both ends: left = 0, right = n-1.
  2. Calculate the current area: min(height[left], height[right]) * (right - left).
  3. Update the maximum area found so far.
  4. Decision: Compare the heights of left and right. Move the pointer pointing to the shorter line inwards.
    • If height[left] < height[right], increment left.
    • Else, decrement right.
  5. Repeat until the pointers meet.

Interactive Walkthrough

Step 1 / 1

Initializing...

1x

Watch how we greedily eliminate the shorter line.

Previous Problem
Two Sum II - Sorted Array
Next Problem
3Sum

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.