# Very simple O(n) solution

• The idea is : to compute area, we need to take min(height[i],height[j]) as our height. Thus if height[i]<height[j], then the expression min(height[i],height[j]) will always lead to at maximum height[i] for all other j(i being fixed), hence no point checking them. Similarly when height[i]>height[j] then all the other i's can be ignored for that particular j.

class Solution {
public:
int maxArea(vector<int> &height)
{
int j=height.size()-1,i=0,mx=0;

while(i<j)
{
mx=max(mx,((j-i)*(min(height[i],height[j]))));

if(height[i]<height[j])
i++;
else if(height[i]>=height[j])
j--;
}
return mx;
}
};

• Don't post solution here.

• Don't view others' solutions before thinking yourself. :p

And for those who really understand this solution:

class Solution {
public:
int maxArea(vector<int> &height) {
if (height.empty()) return 0;
int result = 0;
int l = 0;
int r = height.size() - 1;
while (l < r) {
int area = (r - l) * min(height[l], height[r]);
result = max(result, area);
if (height[l] < height[r]) {
do {
l++;
} while (l < r && height[l-1] >= height[l]);
} else {
do {
r--;
} while (r > l && height[r+1] >= height[r]);
}
}
return result;
}
};

Thanks to @albja16, my algorithm can be further optimized. Welcome to try, guys!

• if we may slant the container, is there any O(n) algorithm？

• Great Solution

• Brilliant solution.

• Yes , only small change in compute area

• Very convincing reasoning!

• Isn't it the same with franticguy's solution?

• Good solution. But I beg to differ a little: as for each inner iteration "do-while", you only need to consider the point value bigger than the border point value h[i], h[j]. e.g: 5,4,2,3,6,7,5,8, at first i=0, j=7, the next value that need computing should be h[4] = 6.

• this further optimized seems cost more time..I dont know why

• Excellent solution

• same here, just using else not else if

public int MaxArea(int[] height) {
int left = 0;
int right = height.Length - 1;
int maxArea = 0;

while (left < right)
{
int area = (right - left) * Math.Min(height[left], height[right]);
if (area > maxArea) maxArea = area;

if (height[left] > height[right]) right--;
else left++;
}
return maxArea;
}

• @franticguy why the calculation formula is maxArea=min(height[i],height[j])|j-i|,not regard as a Trapezoid,and the calculation formulation is maxArea=(height[i]+height[j])|j-i|/2

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.