mafeshsho8lmafeshsho8l
Get Started
All coding questions

Container With Most Water

medium
Blind 75NeetCode 150arraystwo-pointersgreedy

Problem

Given a list of non-negative heights, each representing a vertical line on a number line, find two lines that together with the x-axis hold the most water. Return that maximum area.

Examples

Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Lines at positions 1 and 8 give area min(8,7) * 7 = 49.
Input: heights = [1, 1]
Output: 1
Two unit lines one apart.

Constraints

  • • 2 <= heights.length <= 10^5
  • • 0 <= heights[i] <= 10^4
Hints(tap to reveal)
  • 1. Area is the shorter line times the distance.
  • 2. Moving the taller line never helps; move the shorter.
Optimal approach(spoiler)
  1. Place pointers at both ends and compute the bounded area.
  2. The area is the smaller height times the index distance.
  3. Move the pointer at the shorter line inward, since that is the limiting side.
  4. Track the maximum area throughout.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor