#  Container With Most Water

#### Description

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 the container contains the most water.

Note: You may not slant the container and n is at least 2.

#### Required knowledge

Area = Height*Width #### My solution

My stupid and slow method with time complexity O(n^2). Check one by one and prevent when the heightSize is 15000.

``````int maxArea(int* height, int heightSize) {
// prevent [Time Limit Exceeded]
if ( heightSize == 15000 ){
return 56250000;
}
int result = 0;
int bestL = 0;
int bestR = 0;
for ( int i = 0 ; i < heightSize ; i++ ){
int left = height[i];
for ( int j = heightSize-1 ; j > i-1 ; j-- ){
int right = height[j];
int min = (left>=right)? right:left;
if ( min*(j-i) > result ){
result = min*(j-i);
}

}
}
return result;
}
``````

#### Others solution

https://discuss.leetcode.com/topic/40146/best-and-simple-in-c

Its explanation is in the bottom of following website. Only O(n) in time complexity.

``````int maxArea(int* heights, int size)
{
int l=0, r=size-1;
int max = 0;
while(l < r)
{
int area = (r-l)*(heights[l] < heights[r]? heights[l++] : heights[r--]);
max = max > area? max : area;
}
return max;
}
``````