A generalization of the two-pointer technique: start from both ends and converge toward the center, making a greedy choice at each step about which pointer to move.
Use when: you need to maximize or minimize something across pairs of elements, especially with a width/distance component.
Classic application: given vertical lines on a number line, find the two lines that form the container holding the most water. The area depends on both the distance between lines (width) and the shorter line (height).
The greedy insight: we always move the pointer at the shorter line. Why? The current area is limited by the shorter side. Moving the taller side inward can only reduce width without any chance of increasing the limiting height.
Trace: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
lo=0(1), hi=8(7): area = 8*1 = 8, move lo (shorter) lo=1(8), hi=8(7): area = 7*7 = 49, move hi (shorter) lo=1(8), hi=7(3): area = 6*3 = 18, move hi … best = 49
func maxContainer(heights []int) int {
lo, hi := 0, len(heights)-1
best := 0
for lo < hi {
width := hi - lo
height := min(heights[lo], heights[hi])
area := width * height
if area > best {
best = area
}
if heights[lo] < heights[hi] {
lo++
} else {
hi--
}
}
return best
}
func main() {
fmt.Println(maxContainer([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
fmt.Println(maxContainer([]int{1, 1}))
fmt.Println(maxContainer([]int{4, 3, 2, 1, 4}))
}