Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Start with the widest container: the first and the last line.
  2. 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