Container With Most Water

1. Problem Description

You are given n non-negative integers a1, a2, ..., an, where each number represents a point (i, ai) in the coordinate system. Draw n vertical lines whose endpoints are (i, ai) and (i, 0). Find two lines that, together with the x-axis, form a container that can hold the most water.

2. Approach

1. Approach 1
   • Brute force
   • Compute the rectangle area as (j-i) * min(a[i], a[j]) and take the maximum
   • Enumerate all pairs
2. Approach 2
   • Two pointers
   • Put the left pointer at the far left and the right pointer at the far right, then compute the current area
   • Move the shorter side inward
   • Why move the shorter side rather than the taller side
     • Whether moving the shorter or taller side, the key question is whether the new shorter side becomes taller
     • The moved line has only three possibilities: shorter than the original shorter side, taller than it, or equal to it
     • If the taller side is moved inward, the new line can be:
       • 1. Shorter than the original shorter side, making the new shorter side shorter
       • 2. Equal to or taller than the original shorter side, leaving the shorter side unchanged
     • Therefore, moving the taller side inward cannot make the new shorter side taller

3. Implementation

3.1. Brute Force

func maxArea(height []int) int {
	res := 0

	for i := 0; i < len(height); i++ {
		for j := i + 1; j < len(height); j++ {
			res = Max(res, (j-i)*min(height[i], height[j]))
		}
	}
	return res
}

3.2. Two Pointers

func maxArea(height []int) int {
    left := 0
    right := len(height)-1
    res := 0
    for left < right {
        if height[left] < height[right] {
            res = max(res, (right-left)*height[left])
            left++
        } else {
            res = max(res, (right-left)*height[right])
            right--
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• Container With Most Water (Two-Pointer Method, Illustrated Explanation) - LeetCode