Container With Most Water

Given N non-negative integers a1,a2,….an where each represents a point at coordinate (i, ai). N vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i,0). Find two lines, which together with x-axis forms a container, such that it contains the most water.

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

long long maxArea(long long A[], int len)
{
    long long res = 0, l = 0, r = len - 1;
    while(l < r) {
        res = max(res, (r - l) * (min(A[r], A[l])));
        if(A[l] < A[r]) l++;
        else r--;
    }
    return res;
}

• Time : O(n)
• Space : O(1)
  • range of A[i] is [0 ... 100] so space is biggest stack size is 100 witch is constant O(1)
  • also, stack is constant, time complexity became O(n)

long long maxArea(long long A[], int len)
{
    vector<int> st;
    long long res = 0;
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < st.size(); j++) {
            long long h = min(A[i], A[st[j]]), w = i - st[j];
            res = max(res, h * w);
        }

        if(st.empty() or A[st.back()] < A[i]) st.push_back(i);
    }
    return res;
}