[11] Container With Most Water

© Jarvus Chen / www.jarvus.net

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.

( https://leetcode.com/articles/container-most-water/ )

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;
}