Container With Most Water
Medium · Two Pointers · Array · Two Pointers · Greedy
Problem
height[i] is the height of a vertical line at position i. Pick two lines so that they and the x-axis form a container holding the most water, and return that amount.
The water held by two lines is the distance between them times the shorter of the two.
Examples
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
The lines at index 1 and 8: width 7, limiting height 7.
Input: height = [1,1] Output: 1
Width 1, height 1.
Constraints
- 2 <= len(height) <= 10^5
- 0 <= height[i] <= 10^4
Approaches
- Brute force — every pair — time O(n²), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
