Description Link to heading

11.container-with-most-water

Solution Link to heading

The violent solution of this problem has a time complexity of $O(n^2)$, to reduce the time complexity, we consider two-pointers.

So, we need determine how left pointer l and right pointer r will meet each other:

  • if (height[l] >= height[r]), the capacity depends on height[r]. If l++, the capacity will become smaller, so we should r--.
  • if (height[l] < height[r]), the capacity depends on height[l]. If r--, the capacity will become smaller, so we should l++.

Code Link to heading 

#include <vector>
using std::vector;
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int res = 0;
        while (l < r) {
            if (height[l] >= height[r]) {
                res = max(res, (r - l) * height[r]);
                r--; // l++ will make capacity smaller
            } else {
                res = max(res, (r - l) * height[l]);
                l++; // r-- will make capacity smaller
            }
        }
        return res;
    }
};