Solving Leetcode 11: Container With Most Water

Problem:

From Leetcode

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

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

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

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.

From the start we can tell that this is an array question. When it comes to this question it seems that we will be comparing elements with each other. One of the first approach to this problem is to use a double for loop. Unfortunately we know that a double for loop runs in O(N^2) time, which is very inefficient.

2-Pointer Solution

The ideal solution would be to have two pointers, we could call them start and end. The start pointer will start at the beginning of the array (index 0) and the end pointer will start at the end. (height.length -1). Note that we want the index of the array start and end, NOT the element.

Next we know that by starting at each end we can check whether or not the previous or next element is higher or or not. If so we set the new pointer to higher element and update the area.

1. Keep two index, start= 0 and end = n-1 and a value area that stores the maximum area.
2. Run a while loop until first is less than the last.
3. Update the area with maximum of area and min(array[first] , array[last])*(last-first)
4. if the value at array[first] is greater the array[last] then update last as last – 1 else update first as first + 1
5. Print the maximum area.

Code Here:

class Solution {
    public int maxArea(int[] height) {

        int area = 0;

        int start = 0;

        int end = height.length - 1;

        while(start < end){
            int top = Math.min(height[start], height[end]);

            int newArea = top*(end-start);
            area = Math.max(area, newArea);

            if(height[start]< height[end]){
                start++;
            }
            else{
                end--;
            }
        }
     return area;   
    }
}

We can find the maximum area under a histogram using two pointers. The pointers start at the beginning and end of the histogram, and we move them inward until they meet. At each step, we calculate the area of the rectangle formed by the two pointers and the current height of the histogram. The maximum area is the largest area we calculate.

This algorithm is simple to implement and has a time complexity of O(n). It is a good choice for finding the maximum area under a histogram when the histogram is large.