Container With Most Water

ID: 11; medium

Solution 1 (Java)

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
           for (int j = i + 1; j < height.length; j++) {
               int w = j - i;
               int h = Math.min(height[i], height[j]);
               maxArea = Math.max(maxArea, w * h);
           }
        }
        return maxArea;
    }
}

This is the brute force solution that iterates every possible areas that can be formed by the heights. This will not pass the LeetCode time constraint despite of its correctness.

Solution 2 (Java)

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int w = right - left;
            int h = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, w * h);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

This is the two-pointer approach.

The best intuition for this approach I have come across is the following: To ensure the maximum area, there are two things in consideration: height and width. To start with, we have already had the largest width (by starting left = 0 and right = height.length - 1. When we consider left and right, if the left is shorter, we move the left pointer to the right because the current area is already the maximum area that can be formed by the left height. Namely, any movement of the right pointer to left would decrease the area. The same is for the other case for the right pointer.

You may also do a rigorous proof such as proof by contradiction.

TL;DR: Each step we are can only be improving the situation (not making it worse, i.e., decreasing the area). This is similar to the idea of proving a greedy algorithm.