Container With Most Water
LeetCode #11 · Medium · Two Pointers · C++ solution with worked-out approach and complexity analysis.
Approach
Two Pointers
Start with widest container (left and right ends). Move the pointer with smaller height inward to potentially find a taller line.
Time
O(n)
single pass with two pointers
Space
O(1)
constant extra space
Problem description(from LeetCode)
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most 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
- Note:
- The vertical lines are [1,8,6,2,5,4,8,3,7]. The max area is between index 1 and 8, which is min(8,7) * (8-1) = 49.
Example 2
- Input:
- height = [1,1]
- Output:
- 1
Constraints
- •n == height.length
- •2 <= n <= 10^5
- •0 <= height[i] <= 10^4
C++ Solution
solution.cpp
class Solution {
public:
int maxArea(vector<int> &height) {
int l = 0, r = height.size() - 1;
int res = 0;
while (l < r) {
int area = min(height[l], height[r]) * (r - l);
res = max(res, area);
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return res;
}
};