Leetcode: Container With Most Water

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.

Understand the problem:
The problem actually asks you to find out the maximum (j - i) * min(ai, aj). Therefore, the most straight-forward way is an O(n^2) solution which you iterate every possible pair of i and j, and calculate the (j - i) * min(ai, aj).

Solution:
Since the area is calculated as (j - i) * min(ai, aj), we can start with the maximum width. In other words, we use two pointers, low points to 0, and high points to length - 1. We calculate the area. If height of lo is smaller than the height of hi, move lo one right step. Else, move hi one step left. 

The algorithm works simply because we decrease the width, we must increase the height. Since the height is bounded by the minimum number of ai and aj, we must move the minimum height; otherwise, we can never ever get the maximum area. Moving the pointer with smaller height can make it possible to get the maximum area.

Code (Java):

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) 
            return 0;
            
        int lo = 0;
        int hi = height.length - 1;
        int max = 0; 
        
        while (lo < hi) {
            max = Math.max(max, (hi - lo) * Math.min(height[lo], height[hi]));
            if (height[lo] < height[hi]) lo++;
            else hi--;
        }
        return max;
    }
}

Discussion:
Since we only iterate the array once, the time complexity is O(n). The space complexity is O(1).

Summary:
Take-away message of the problem is: first, understand the problem thoroughly. For such kind of application problems, it is key to generalize the problem in a programmer's perspective. For e.g. this problem actually asks you calculate the maximum area. 

Secondly, the two pointers solution can be commonly used in many other questions, such as 2 sum. Be familiar with this idea.