Challenge Description
Given n nonnegative 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 xaxis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Example:

Native solution
According the challenge description, a naive solution is not hard to figure out.
Time complexity: $O(N^2)$, as we enumerate all the pairs of index in array.

Approach with two pointers
This approach is clever and elegant! It’s time complexity: $O(N)$.
But how to prove it’s right?
I get a nonformal proof from intuition.
 We start with (0, size1), the result pair maybe in the inner loop, so we narrow one index try to enumerate the pairs.
If we must to narrow one index, which one to choose? If we narrow the index with higher height, the decreased water must larger, so the only choice is to narrow the index with smaller height.
class Solution {
public:
int maxArea(vector<int> &height) {
int ans = 0;
int head = 0;
int tail = height.size()  1;
while(head < tail) {
int area = abs(tail  head) * min(height[head], height[tail]);
ans = max(area, ans);
if(height[head] < height[tail])
head++;
else
tail;
}
return ans;
}
};
Join my Email List for more helpful insights, It's Free!😋