Friday, January 17, 2014

Leetcode: Container With Most Water

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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

Solution:
The algorithm is very simple, we start using the whole interval [1,n] as the base and we reduce it on the side that its height is smaller. We actualize the area if the new one is larger than the previous and we keep till the base has 0 width.

Code:

public class Solution {
    public int maxArea(int[] height) 
    {
       int start=0;
       int end= height.length-1;
       int area= Math.min(height[start],height[end])*(end-start);
       while (start < end)
       {
            int areaT= Math.min(height[start],height[end])*(end-start);
            area = areaT > area ? areaT : area;
            if(height[start]>height[end])
                end--;
            else
                start++;
       }
       return area;
    }
}

No comments :

Post a Comment