# A fast and easy-understand cpp solution

• ``````    int maxArea(vector<int> &height) {
int l(0), r=height.size()-1, result(0);
while(l < r){
if(height[l] < height[r]){
result =  max(result, height[l] * (r - l));
int pivot = height[l++];
while(l < r && height[l] <= pivot) ++l;
}else{
result = max(result, height[r] * (r - l));
int pivot = height[r--];
while(l < r && height[r] <= pivot) --r;
}
}
return result;
}``````

• python version:

``````  def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l, r, result = 0, len(height)-1, 0
while l < r:
if height[l] < height[r]:
result = max(result, (r-l) * height[l]);
pivot = height[l]
l += 1
while l < r and height[l] <= pivot: l+=1
else:
result = max(result, (r-l) * height[r]);
pivot = height[r]
r -= 1
while l < r and height[r] <= pivot: r-=1
return result``````

• Is this solution a sort of greedy algorithm ?

• As I see this algorithm has 3 parts.

## 1. Checking if there are more possiblities

Keeping the invariant of `l < r` means that left is on the left side of right. If `l >= r`, it means that:

• the left is either the same as right (0-width -> 0-area)
• or they're in the wrong order (negative area).

This is used in part 3 too.

## 2. Finding the max

``````if (height[l] < height[r]) {
result = max(result, height[l] * (r - l));
} else {
result = max(result, height[r] * (r - l));
}
``````

which is the same as

``````result = max(result, min(height[l], height[r]) * (r - l));
``````

Consider a container with two sides (`l`/`r`):

``````  |    overflow--._
|      ----------\
|  |            | \
|  |  |         |
--l---------------r-------
``````

the area of the container is given by the smaller height (`r`) and their distance (`r - l`). Cannot choose the other side (`l`) because the water would just overflow. This is symmetric if we draw the column heights the opposite.

## 3. Skipping the values that can't be better

``````if (height[l] < height[r]) {
int pivot = height[l++];
while(l < r && height[l] <= pivot) ++l;
} else {
int pivot = height[r--];
while(l < r && height[r] <= pivot) --r;
}
``````

Removing the optimizations (post-increments) and the bounds checking (`l < r`, see part 1):

``````if (height[l] < height[r]) {
int pivot = height[l];
while (height[l] <= pivot) ++l;
} else {
int pivot = height[r];
while (height[r] <= pivot) --r;
}
``````

it's easier to see that it's looking for the next element that is bigger than the pivot.
The two branches are just for choosing which side to start looking for a better possibility. The smaller side must be chosen, because the area is contained by `min(height[l], height[r])` (see part 2).

Anything smaller than or equal to the pivot can be skipped because:

1. the distance between current `l` and `r` is getting smaller, so area getting smaller too
2. if a height is smaller than pivot the area is smaller too

If we find a bigger than pivot height we can hope for a bigger area (depending on how much taller it is).
The post-increment optimization is just there to not run an unnecessary loop of the `while` for the pivot itself.