Container With Most Water

Problem statement

Each index i is a vertical line of height height[i]. Choose two lines that form a container with the x-axis and maximize how much water that container can hold (min height × width).

Example:

Input:

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

Expected output:

49

Why: lines of height 8 and 7 (width 7) give area 49.

Practice on LeetCode: Container With Most Water

Golang Solution

Start with pointers at both ends. The area is limited by the shorter line and the width j - i. Move the pointer at the shorter line inward — that is the only way the area might increase — and track the maximum.

Time: O(n)
Space: O(1)

func maxArea(height []int) int {
	ans := 0
	i, j := 0, len(height)-1

	for i < j {
		var qty int
		if height[i] < height[j] {
			qty = height[i] * (j - i)
			i++
		} else {
			qty = height[j] * (j - i)
			j--
		}
		if qty > ans {
			ans = qty
		}

	}

	return ans
}