Given non-negative integers , where each represents a point at coordinate . vertical lines are drawn such that the two endpoints of line is at and . 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 . We take a "closing into the center" approach. Starting with . We initialize the largest area as . Next, we try want to move. We have two options: increase or decrease . Let me state a lemma first:

if .

Proof:

- If , then .
- If , then .

This tells us if and we increase by 1, we can rule out the since it must be smaller than . Similarly, we can decrease by 1 if . This gives us the iterative structure of the program. We stop until meets . Therefore this is a 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

Google

Feb 18, 2014@ 16:44:36Very good explanation.