Container With Most Water

Medium Arrays

Given heights of vertical lines, find two lines that together with the x-axis hold the most water. Two-pointer, O(n).

Sample input

[1, 8, 6, 2, 5, 4, 8, 3, 7]

Sample output

Solution

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))

function maxArea(height) {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    best = Math.max(best, (right - left) * Math.min(height[left], height[right]));
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));

public class Main {
    static int maxArea(int[] height) {
        int left = 0, right = height.length - 1, best = 0;
        while (left < right) {
            best = Math.max(best, (right - left) * Math.min(height[left], height[right]));
            if (height[left] < height[right]) left++;
            else right--;
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }
}

fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var best = 0
    while (left < right) {
        best = maxOf(best, (right - left) * minOf(height[left], height[right]))
        if (height[left] < height[right]) left++ else right--
    }
    return best
}

fun main() {
    println(maxArea(intArrayOf(1, 8, 6, 2, 5, 4, 8, 3, 7)))
}

func maxArea(_ height: [Int]) -> Int {
    var left = 0, right = height.count - 1, best = 0
    while left < right {
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }
    return best
}

print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))

int maxArea(List<int> height) {
  var left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    final h = height[left] < height[right] ? height[left] : height[right];
    final area = (right - left) * h;
    if (area > best) best = area;
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return best;
}

void main() {
  print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(const vector<int>& height) {
    int left = 0, right = height.size() - 1, best = 0;
    while (left < right) {
        best = max(best, (right - left) * min(height[left], height[right]));
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

int main() {
    cout << maxArea({1, 8, 6, 2, 5, 4, 8, 3, 7}) << endl;
    return 0;
}

#include <stdio.h>

int maxArea(int *height, int n) {
    int left = 0, right = n - 1, best = 0;
    while (left < right) {
        int h = height[left] < height[right] ? height[left] : height[right];
        int area = (right - left) * h;
        if (area > best) best = area;
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

int main() {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    printf("%d\n", maxArea(height, 9));
    return 0;
}