011. Container With Most Water

At a Glance

• Topic: two-pointers
• Pattern: Two Pointers
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Adobe
• Frequency: Very High
• LeetCode: 11

Problem (one-liner)

Given non-negative integer heights at indices 0..n-1, pick two vertical lines so the x-distance times the shorter height maximizes "water" area. Return that maximum area.

Recognition Cues

• "Maximum area" between two indices in an array
• "Water", "container", height vs width tradeoff
• Two movable boundaries and a min(height) rule

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n²) time / O(1) space — try every pair (left, right).
• Better — same brute until you prove greedy move — still O(n²) without the insight.
• Optimal — O(n) time / O(1) space — start at both ends; always discard the shorter side because keeping it cannot beat moving the taller side for larger area.

Optimal Solution

Go

func maxArea(height []int) int {
	left, right := 0, len(height)-1
	best := 0
	for left < right {
		width := right - left
		h := height[left]
		if height[right] < h {
			h = height[right]
		}
		area := width * h
		if area > best {
			best = area
		}
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return best
}

JavaScript

function maxArea(heights) {
	let left = 0;
	let right = heights.length - 1;
	let best = 0;
	while (left < right) {
		const width = right - left;
		const shorter =
			heights[left] < heights[right] ? heights[left] : heights[right];
		const area = width * shorter;
		if (area > best) {
			best = area;
		}
		if (heights[left] < heights[right]) {
			left++;
		} else {
			right--;
		}
	}
	return best;
}

Walkthrough

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

Invariant: every discarded shorter boundary cannot participate in a better pair with the opposite fixed taller side already considered.

Edge Cases

• Length 2
• All heights equal
• Strictly increasing / decreasing heights
• Zero heights

Pitfalls

• Moving both pointers at once
• Using max of heights instead of min for area
• Integer overflow on product (use 64-bit if required by constraints)

Similar Problems

• 15. 3Sum — sort + two pointers for triplets.
• 125. Valid Palindrome — two pointers from ends on sequence constraints.
• 167. Two Sum II — Input Array Is Sorted — inward pointers on sorted array.

Variants

• "Trapping rain water" (different geometry — often DP or two pointers with prefix max).
• K containers / more columns — problem changes entirely.

Mind-Map Tags

#two-pointers #greedy-area #inward-pointers #max-min-product