Leetcode–Container With Most Water

The Problem:

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.

Notes:

  1. Use two pointers, start from beginning and end, each iteration move the index which has smaller value towards middle.
  2. Only update the max Area when new index has bigger value than previous value, since the distance already decreasing, if the height is also decreasing then can’t get a larger area than previous.
  3. Mistake I made: Be careful in the inner while loop condition, still need to always hold start<end.

Java Solution:

public class Solution {
    public int maxArea(int[] height) {
        int start = 0;
        int end = height.length-1;
        int maxA = 0;
        while(start<end){
            if(height[start] >= height[end]){
                maxA = Math.max(maxA, (height[end]*(end-start)));
                int prev = height[end];
                end--;
                while(end > start && height[end] <= prev){
                    end--;
                }
            }
            else{
                maxA = Math.max(maxA, (height[start]*(end-start)));
                int prev = height[start];
                start++;
                while(end > start && height[start] <= prev){
                    start++;
                }
            }
        }
        return maxA;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s