Problem statement

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(depth is constant across containers). Return the area(that the 2 lines and the X axis make) of container which can store the max amount of water. Notice that you may not slant the container.

Solution

Brute force

Keeping the height of the container constant, we can find the width of the container by iterating over all possible combinations of two lines. This would take O(n^2) time and O(1) space.

Optimized

We can use a two pointer approach to solve this problem in O(n) time and O(1) space. We start with two pointers, one at the start and one at the end of the array. We calculate the area of the container formed by these two lines and move the pointer with the smaller height inwards. This is because the area of the container is limited by the smaller height. We keep doing this until the two pointers meet. We return the maximum area we have seen so far.

Code

Brute force

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int area_with_most_water(vector<int> list) {
  int len = list.size();
  if (len < 2)
    return 0;

  int max_area = 0;
  for (int i = 0; i < len; i++) {
    int left_height = list[i];
    for (int j = i + 1; j < len; j++) {
      int distance = j - i;
      int right_height = list[j];
      int min_height = right_height > left_height ? left_height : right_height;
      int area = min_height * distance;
      if (area > max_area) {
        max_area = area;
      }
    }
  }
  return max_area;
}

int main() {
  vector<int> arr = {3, 1, 2, 4, 5};
  printf("Largest storeable area: %d\n", area_with_most_water_fast(arr));
  return 0;
}

Optimized

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;


int area_with_most_water_fast(vector<int> lines) {

  int len = lines.size();

  // there needs to be atleast 2 lines to form an area with the x-axis as basis
  if (len <= 1)
    return 0;

  int start = 0;
  int end = len - 1;

  int area = 0;

  while (start < end) {

    int distance = end - start;
    area = max(area, min(lines[start], lines[end]) * distance);

    if (lines[start] < lines[end]) {
      start += 1;
    } else {
      end -= 1;
    }
  }
  return area;
}

int main() {

  vector<int> arr = {3, 1, 2, 4, 5};

  printf("Largest storeable area: %d\n", area_with_most_water_fast(arr));

  return 0;
}