Checking every pair of lines is O(n²). The two pointers idea is to start with the widest container and then only move the pointer that is limiting the result, because moving the other one can never help.
You are given a list height where height[i] is the height of a vertical line at position i. Choose two lines so that, together with the x-axis, they form a container holding the most water. Return the maximum amount of water: (j - i) * min(height[i], height[j]).
Examples
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: Lines at index 1 (height 8) and index 8 (height 7): width 7 * height 7 = 49.
Input: height = [1, 1]
Output: 1
Constraints
2 <= len(height) <= 10**40 <= height[i] <= 10**4- Aim for O(n) time.
Goals
- Start with the widest possible pair and shrink inward
- Justify which pointer to move by reasoning about what could possibly improve the answer
- Replace an O(n²) pair enumeration with an O(n) two-pointer scan