Container with most water

Leetcode link:
Q:
Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container. 


A:
Given line i and line j, one can easily come up with: \[ Area[i][j] = min(height[i], height[j]) * (j-i) \]
So an \( O(n^2) \) solution is fairly easy to get.


To decrease the time complexity, tricks and pruning are all what you need. Suppose we found an solution from i to j \( (i<j) \), and we assume \( height[i] < height[j] \). Then \( height[i] \) is dominant, which means if we decrease j, there will be no area larger than \( Area[i][j] \). This should be very easy to verify.


With this pruning, in order to investigate all possible i and j combinations, we start with \( i = 0 \) and \( j = height.size()-1 \) and shrink i and j inward, resulting the following simple code:

int maxArea(vector<int> &height) {
    if(height.size() <= 1) return 0;
    // idea of this program: If found one candidate [A[i], A[j]], 
    // if A[i] < A[j] then A[i] is dominate. all [A[i], A[j-k]] (k>0) 
    // will not generate area larger than [A[i], A[j]]. The only 
    // candidates can be achieved by moving j.
    int low, high;
    low = 0;
    high = height.size()-1;
    int maxarea = min(height[high], height[low]) * (high-low);
    while(low != high) {
        maxarea = max(maxarea, min(height[high], height[low]) * (high-low));
        if(height[low] < height[high]) low++;
        else high--;
    }
    return maxarea;
}