Container With Most Water Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: Array, Two Pointers, Greedy
Problem Statement
Given n non-negative integers height where each represents a point at coordinate (i, height[i]), find two lines that together with the x-axis form a container that can hold the maximum amount of water.
Return the maximum amount of water a container can store.
Examples
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The maximum area is obtained by choosing height[1] = 8 and height[8] = 7, which gives area = min(8,7) × (8-1) = 7 × 7 = 49.
Example 2:
Input: height = [1,1]
Output: 1
Explanation: The maximum area is obtained by choosing height[0] = 1 and height[1] = 1, which gives area = min(1,1) × (1-0) = 1 × 1 = 1.
Example 3:
Input: height = [4,3,2,1,4]
Output: 16
Explanation: The maximum area is obtained by choosing height[0] = 4 and height[4] = 4, which gives area = min(4,4) × (4-0) = 4 × 4 = 16.
Example 4:
Input: height = [1,2,1]
Output: 2
Explanation: The maximum area is obtained by choosing height[0] = 1 and height[2] = 1, which gives area = min(1,1) × (2-0) = 1 × 2 = 2.
Intuition
The key insight is that the area of water contained between two lines is determined by the shorter line and the distance between them. We can use two pointers to find the optimal solution.
Approach
Approach 1: Two Pointers (Optimal)
1. Use two pointers: left at start, right at end
2. Calculate area = min(height[left], height[right]) × (right - left)
3. Move the pointer with the shorter height inward
4. Keep track of maximum area found
Approach 2: Two Pointers with Early Termination
1. Same as two pointers but with additional optimizations
2. Skip lines that are shorter than current maximum height
3. Early termination when pointers meet
Approach 3: Brute Force
1. Check all possible pairs of lines
2. Calculate area for each pair
3. Keep track of maximum area
Dry Run
Let's trace through Example 1: height = [1,8,6,2,5,4,8,3,7]
Two Pointers Approach:
- left=0, right=8: area = min(1,7) × (8-0) = 1 × 8 = 8, maxArea = 8
- left=1, right=8: area = min(8,7) × (8-1) = 7 × 7 = 49, maxArea = 49
- left=1, right=7: area = min(8,3) × (7-1) = 3 × 6 = 18, maxArea = 49
- left=1, right=6: area = min(8,8) × (6-1) = 8 × 5 = 40, maxArea = 49
- left=1, right=5: area = min(8,4) × (5-1) = 4 × 4 = 16, maxArea = 49
- left=1, right=4: area = min(8,5) × (4-1) = 5 × 3 = 15, maxArea = 49
- left=1, right=3: area = min(8,2) × (3-1) = 2 × 2 = 4, maxArea = 49
- left=1, right=2: area = min(8,6) × (2-1) = 6 × 1 = 6, maxArea = 49
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Two Pointers (Optimal)
Time Complexity: O(n) - We traverse the array once
Space Complexity: O(1) - Only need a few variables
Solution 2: Two Pointers with Optimizations
Time Complexity: O(n) - We traverse the array once
Space Complexity: O(1) - Only need a few variables
Solution 3: Brute Force
Time Complexity: O(n²) - Check all pairs
Space Complexity: O(1) - Only need a few variables