Problem intuition
- Brute force tries every pair and computes the area directly.
- The optimal move is to start from the widest container and shrink only the shorter wall, because moving the taller wall cannot increase the height bottleneck.
Solution
The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.
Solution 1
Brute force all pairs
- Compute the area for every pair of lines and keep the largest value.
- This is easy to reason about, but it is quadratic.
- Time complexity: O(n^2)
- you compute the area for every pair of lines using two nested loops.
- Space complexity: O(1)
- the algorithm only tracks the current best area and a few loop variables.
Solution 2
Two pointers from the widest span
- Begin at both ends so you start with the widest possible container.
- Always move the shorter wall inward because that is the only move that can improve the bottleneck height.
- Time complexity: O(n)
- each pointer moves inward at most once across the array.
- Space complexity: O(1)
- only two pointers and the running best area are stored.