Container With Most Water

Problem statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container such that the container contains the most water.

Return the maximum amount of water a container can store.

Example:

Input:

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

Expected output:

49

Explanation: The lines at index 1 (height 8) and index 8 (height 7) form an area of 7 * (8 - 1) = 49.

If you would like to solve the problem on LeetCode, here is the link to the problem: LeetCode problem link

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
}