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