How to Solve Container With Most Water on LeetCode
The Container With Most Water problem is a classic array and two-pointer challenge.
Problem Statement
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i are at (i, ai) and (i, 0). Find two lines, which together with the x-axis forms a container, such that the container contains the most water.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The max area is between the lines at positions 1 and 8 (8*7=56, but 7 is the limiting height).
Why This Problem Matters for Interviews
- Tests your grasp of the two-pointer strategy
- Checks your ability to optimize brute force solutions
- Appears frequently in FAANG interviews
Approach to Container With Most Water
Two-Pointer Technique (Optimal)
Start with two pointers at both ends and move the pointer at the shorter line inward.
Time Complexity: O(n)
Space Complexity: O(1)
def maxArea(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
max_water = max(max_water, width * min(height[left], height[right]))
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
Key Interview Talking Points
- Why brute force (O(n^2)) is too slow
- How the two-pointer method works and why it’s optimal
- Always move the shorter line's pointer
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two-Pointer Method | O(n) | O(1) |
Pro Interview Tips
- Draw the height array to visualize areas
- Explain why moving the shorter line is key
- Know edge cases (all same height, length 2)