Practice › Hashing & Two Pointers
Container With Most Water
Medium · Hashing & Two Pointers · Asked at Amazon, Google, Microsoft, Adobe, Goldman Sachs
Lines are drawn at x = 0..n−1 with heights h[i]. Pick two lines that, with the x-axis, hold the most water. Print that maximum area (width × smaller height).
Input
First line: n. Second line: n heights.
Output
The maximum area.
Constraints
- 2 ≤ n ≤ 10^5
- 0 ≤ h[i] ≤ 10^4
Two pointers from both ends; always move the shorter line inwards.
Example 1
Input
9 1 8 6 2 5 4 8 3 7
Output
49
Example 2
Input
2 1 1
Output
1
Hints
- Start with the widest container: the first and the last line.
- Moving the taller line inwards can never help (width shrinks, height is still capped by the shorter one). So always move the shorter line.
Approach
Put pointers at both ends. The area is (r − l) × min(h[l], h[r]). Any container that keeps the shorter line and moves the other one inwards is narrower and no taller, so the shorter line can be dropped: move it inwards. Each step discards one line, giving O(n). The area is below 10^9, but 64 bits costs nothing.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> h(n);
for (auto &x : h) cin >> x;
int l = 0, r = n - 1;
long long best = 0;
while (l < r) {
best = max(best, (r - l) * min(h[l], h[r]));
if (h[l] < h[r]) l++;
else r--;
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
h = data[1 : data[0] + 1]
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, (r - l) * min(h[l], h[r]))
if h[l] < h[r]:
l += 1
else:
r -= 1
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] h = new long[n];
for (int i = 0; i < n; i++) h[i] = sc.nextLong();
int l = 0, r = n - 1;
long best = 0;
while (l < r) {
best = Math.max(best, (r - l) * Math.min(h[l], h[r]));
if (h[l] < h[r]) l++;
else r--;
}
System.out.println(best);
}
}Solve Container With Most Water online · All practice problems