Introduction
LeetCode 11: Container With Most Water is a popular problem that challenges you to think greedily and efficiently. The naive approach can be slow, but with the clever use of two pointers, you can solve it in linear time.
In this article, we'll walk through the logic behind the two-pointer technique and implement the solution in Go (Golang).
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 i-th line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container such that the container holds the most water.
Return the maximum amount of water a container can store.
Examples
go
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
go
Input: height = [1,1]
Output: 1
Visual Understanding
Each pair of lines and the x-axis form a container. The area is calculated as:
arduino
area = min(height[i], height[j]) * (j - i)
We want to find the maximum area.
Brute Force Approach (Inefficient)
Check every pair of lines → O(n²) time complexity.
Not suitable for large inputs.
Optimized Approach: Two Pointers
Use two pointers at the start and end of the array. At each step:
- Calculate the area between the two lines.
- Move the pointer that points to the shorter line, hoping for a taller one.
Why This Works:
We want to maximize the height, but since width decreases as we move inward, we only move the shorter line to find a better combination.
Go Implementation
go
package main
import (
"fmt"
)
func maxArea(height []int) int {
left := 0
right := len(height) - 1
maxArea := 0
for left < right {
h := min(height[left], height[right])
width := right - left
area := h * width
if area > maxArea {
maxArea = area
}
// Move the pointer with smaller height
if height[left] < height[right] {
left++
} else {
right--
}
}
return maxArea
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
testCases := [][]int{
{1, 8, 6, 2, 5, 4, 8, 3, 7},
{1, 1},
{4, 3, 2, 1, 4},
{1, 2, 1},
}
for _, heights := range testCases {
fmt.Printf("Input: %v -> Max Area: %d\n", heights, maxArea(heights))
}
}
Step-by-Step Example
For input [1,8,6,2,5,4,8,3,7]:
- Start with left = 0, right = 8
- Compute area = min(1,7) * (8-0) = 1 * 8 = 8
- Move left (since 1 < 7)
- New area = min(8,7) * 7 = 7 * 7 = 49
- Continue moving and comparing…
Final result: 49
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Key Takeaways
- Use two pointers to reduce time complexity from O(n²) to O(n).
- Always move the pointer with the shorter line.
- This problem is a great example of the greedy + sliding window mindset.