(Container With Most Water)

Given n non-negative integers a_{1}, a_{2}, \dots, a_{n}, where each represents a point at coordinate (i, a_{i}). n vertical lines are drawn such that the two endpoints of line i is at (i, a_{i}) 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.

Thoughts:
Mathematically, the solution to the problem is given by \arg\max_{i<j} \min(a_{i},a_{j})\cdot(j-i). We take a "closing into the center" approach. Starting with i = 0, j = n - 1. We initialize the largest area as \min(a_{i},a_{j})\cdot(n-1). Next, we try want to move. We have two options: increase i or decrease j. Let me state a lemma first:
\forall i<k<j, \text{Area}(i,k) < \text{Area}(i,j) if a_{i} < a_{j}.
Proof:

  • If a_{k} \leq a_{i}, then \text{Area}(i,k) = a_{k}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j).
  • If a_{k} > a_{i}, then \text{Area}(i,k) = a_{i}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j).

This tells us if a_{i} < a_{j} and we increase i by 1, we can rule out the \text{Area}(i,i+1) since it must be smaller than \text{Area}(i,j). Similarly, we can decrease j by 1 if a_{i} \leq a_{j}. This gives us the iterative structure of the program. We stop until i meets j. Therefore this is a O(n) algorithm.

Code (C++):

class Solution {
public:
    int maxArea(vector<int> &height) {
        int i =0;
        int j = height.size() - 1;
        int best = min(height[i], height[j]) * (j-i);
        if(height[i] < height[j])
            i++;
        else
            j--;
            
        while(i < j) {
            int area = min(height[i], height[j]) * (j-i);
            if(area  > best)
                best = area;
            
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        return best;        
    }
};

Code (Java):

public class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int best = Math.min(height[i], height[j]) * (j-i);

        if(height[i] < height[j])
            i++;
        else
            j--;
            
        while(i < j) {
            int area = Math.min(height[i], height[j]) * (j-i);
            if(area > best)
                best = area;
            
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        
        return best;
    }
}
Advertisements

1 Comment (+add yours?)

  1. Google
    Feb 18, 2014 @ 16:44:36

    Very good explanation.

    Reply

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

%d bloggers like this: