11. Container With Most Water

/**

 * 11. 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 the line i is at (i, ai) and (i, 0).

 * Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

 * Notice that you may not slant the container.

 * Example 1:

 * Input: height = [1,8,6,2,5,4,8,3,7]

 * Output: 49

 * Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].

 * In this case, the max area of water (blue section) the container can contain is 49.

 */

See the solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ContainerWithMostWater.java

This question is similar to max rectangle in histogram a solution to which I have also included in these explanations here. Please also have a look at that solution as well.

Observation: You are asked to calculate the maximum area of rectangle (container of water). Area is simply width * height. You can start from left and right edges and move inwards until left and right cross while calculating area every time you move inwards. Out of the right and left indexes, you want to move the index inward with the smaller height.

Logic:

1. Start from left and right indexes
2. While left index is less than right index
   1. Take minimum height at left and right index and multiply by width between left and right index
   1. Move the smaller of the left or right indexes inward
   1. If same choose move any one of them inward

Here is the code:

public static int maxArea(int[] height) {
    int maxArea = 0;
    int r = height.length - 1;
    int l = 0;
    while (r > l) {
        int dist = r - l;
        maxArea = Math.max(maxArea, Math.min(height[l], height[r]) * dist);
        if (height[r] > height[l]) {
            l++;
        } else {
            r--;
        }
    }
    return maxArea;
}