Container With Most Water Solution for Capgemini
Company: Capgemini · Difficulty: Medium · 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. The 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. The 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. The area = min(4,4) * (4-0) = 4 * 4 = 16.
Intuition
The key insight is that the area of water contained between two lines is determined by:
1. The height of the shorter line (water level cannot exceed the shorter line)
2. The distance between the two lines (width of the container)
The optimal approach is to use two pointers starting from the ends and move the pointer with the shorter height inward, as this gives us the best chance of finding a larger area.
Approach
Approach 1: Two Pointers (Optimal)
1. Initialize two pointers: left = 0, right = n-1
2. Calculate area = min(height[left], height[right]) * (right - left)
3. Update maxArea if current area is larger
4. Move the pointer with smaller height inward
5. Repeat until left < right
Approach 2: Brute Force
1. Check all possible pairs of lines
2. Calculate area for each pair
3. Keep track of maximum area found
Approach 3: Dynamic Programming (Less Efficient)
1. Use DP to store maximum area for each subarray
2. Build solution bottom-up
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
- height[left] = 1, height[right] = 7
- area = min(1,7) * (8-0) = 1 * 8 = 8
- maxArea = 8
- Move left pointer (shorter height): left = 1
- left = 1, right = 8
- height[left] = 8, height[right] = 7
- area = min(8,7) * (8-1) = 7 * 7 = 49
- maxArea = 49
- Move right pointer (shorter height): right = 7
- left = 1, right = 7
- height[left] = 8, height[right] = 3
- area = min(8,3) * (7-1) = 3 * 6 = 18
- maxArea = 49 (unchanged)
- Move right pointer: right = 6
Continue until left >= right
Key Insights
1. Two Pointers: Start from ends and move inward
2. Greedy Choice: Always move the pointer with smaller height
3. Area Calculation: area = min(height1, height2) * distance
4. Optimal Substructure: Each step considers the best possible area for current positions
Edge Cases
1. Two elements: [1,1] → area = 1
2. All same height: [5,5,5] → area = 10
3. Increasing heights: [1,2,3,4,5] → area = 6
4. Single element: [5] → area = 0 (need at least 2 lines)