Container With Most Water
MediumTwo pointers
height[i] is the height of a vertical line drawn at position i. Any two lines, with the ground between them, form a container.
The water it holds is the distance between the two lines times the height of the shorter one. Return the most water any container can hold.
Examples
Input: height = [2, 5, 4, 8, 3, 6] Output: 20
The lines at indexes 1 and 5, heights 5 and 6, are 4 apart: they hold 5 × 4 = 20.
Input: height = [3, 3] Output: 3
Two lines of height 3, one apart, hold 3.
Constraints
2 ≤ height.length ≤ 10⁵0 ≤ height[i] ≤ 10⁴
Stuck?
Hint 1
Start with the widest container, the two outer lines. Any narrower one only holds more if its shorter side is taller.
Hint 2
Move inward from whichever side is shorter: keeping that line can never beat the container you have just measured.
The idea
Start with the two outer lines, the widest container. Every other container that keeps the shorter of those two lines is narrower and no taller, because the shorter line still caps the water, so that line can be dropped. Moving inward from the shorter side, one line at a time, never skips the best container.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Begin with the widest pair: the first line and the last.
function maxArea(height) { let left = 0; let right = height.length - 1; let best = 0; while (left < right) { best = Math.max(best, Math.min(height[left], height[right]) * (right - left)); if (height[left] < height[right]) left++; else right--; } return best;}The trap
It moves the taller line inward and keeps the shorter one. That looks like a fair choice, since either move narrows the container by one. But the shorter line caps the water, so every container that keeps it holds no more than the pair measured before it, while the line given up might have paired with a tall line further in. The answer comes out too small whenever the best container needs the short outer line to be dropped.
function maxArea(height) { let left = 0, right = height.length - 1, best = 0; while (left < right) { best = Math.max(best, Math.min(height[left], height[right]) * (right - left)); if (height[left] > height[right]) left++; // moves the taller line, keeps the short one else right--; } return best;}