Largest Water Container

medium array two pointers greedy

Problem

An array of non-negative integers describes the heights of vertical lines drawn on the x-axis. Pick two of those lines so that, together with the x-axis, they hold the most water. Return that maximum area.

Inputheights = [3, 1, 4, 6, 2, 5]

Output15

Lines at indices 2 and 5 give width 3 × min(4, 5) = 12. Lines at 0 and 5 give 5 × 3 = 15, the best.

heights (comma-separated, non-negative)

def max_area(h):
    l, r = 0, len(h) - 1
    best = 0
    while l < r:
        area = (r - l) * min(h[l], h[r])
        if area > best:
            best = area
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best

function maxArea(h) {
  let l = 0, r = h.length - 1;
  let best = 0;
  while (l < r) {
    const area = (r - l) * Math.min(h[l], h[r]);
    if (area > best) best = area;
    if (h[l] < h[r]) l++; else r--;
  }
  return best;
}

class Solution {
    public int maxArea(int[] h) {
        int l = 0, r = h.length - 1;
        int best = 0;
        while (l < r) {
            int area = (r - l) * Math.min(h[l], h[r]);
            if (area > best) best = area;
            if (h[l] < h[r]) l++; else r--;
        }
        return best;
    }
}

int maxArea(vector<int>& h) {
    int l = 0, r = (int)h.size() - 1;
    int best = 0;
    while (l < r) {
        int area = (r - l) * min(h[l], h[r]);
        if (area > best) best = area;
        if (h[l] < h[r]) l++; else r--;
    }
    return best;
}

Time: O(n) Space: O(1)