Container With Most Water

Medium

The problem

Each number in the list is the height of a vertical wall standing on a line, one unit apart. Pick two walls to form a container; it holds (distance between the walls) × (height of the shorter wall) units of water. Return the largest amount of water any container can hold.

Example 1
Input: height = [3, 1, 2, 5, 4]
Output: 12
Walls at positions 0 and 4 (heights 3 and 4) are 4 apart: 4 × min(3, 4) = 12.
Example 2
Input: height = [1, 1]
Output: 1
One container: distance 1 × height 1 = 1.

Limits

2 ≤ height.length ≤ 100,000
0 ≤ height[i] ≤ 10,000
The container cannot be tilted

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Area = width × the shorter wall. Starting from the widest container, what is the only way to improve?

The idea

Pointers at both ends; record the area, then move the pointer at the SHORTER wall inward (moving the taller one can never help).

Target: O(n) time, O(1) space

Go function shape

func maxArea(height []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MaxArea: most water between two vertical lines.
// Width only shrinks, so the only way to improve is to move the shorter wall.
func MaxArea(height []int) int {
	best, left, right := 0, 0, len(height)-1
	for left < right {
		h := min(height[left], height[right])
		best = max(best, h*(right-left))
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return best
}

Read the lesson: Two Pointers