Container with Most Water Problem & Solution

See the container with most water problem on LeetCode.

C++ Solution

The runtime complexity of this algorithm is $O(n)$.

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxArea(vector<int>& height) {
    int best = (height.size() - 1) * min(height[0], height[height.size() - 1]);

    int i = 0, j = height.size() - 1;
    while (i < j) {

      // Keeps moving the smallest height towards the center.
      if (height[i] < height[j]) {
        ++i;
      } else {
        --j;
      }

      best = max(best, (j - i) * min(height[i], height[j]));
    }

    return best;
  }
};