LeetCode: Container With Most Water

Given n non-negative integers a₁, a₂, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example 1:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation:

Constrains: 0 < sizeof(heightArray) <= 10^5

Question Link: Container With Most Water

Solution: 

The first brute force way to approach this problem is to start from each line i and check its capacity with all lines j such that i < j < n which is pretty simple.

Code:

Implemented in C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea=0; // Initializing maximum area as 0

        for(int i=0; i<height.size(); i++){
            for(int j=i+1; j<height.size();j++){
                // Going through all pairs (i,j) for maximum container area.
                maxArea = max(maxArea, min(height[i], height[j])*(j-i));
            }
        }
        return maxArea;
    }
};

But the time complexity of this approach is O(n^2) which is not accepted.

Better Approach

The main catch in this question is to find the maximum area which can be caused due to two factors:

1. Bigger Width
2. Bigger Height

Lets firstly maximize the width by taking the two extreme ends of the input array i.e. 0 and n-1 as two pointers and then continue to decrease each end along with calculating area for each case. But question is which end should we decrease?

There are two possibilities:

1. Both pointers’ heights are same
2. They have different heights

If we switch from a pointer having more height, the we are losing a potential pair which can have better area while decreasing the pointer having less height will not cause any trouble. So, we should decrease the pointer having less height. This is a greedy approach, for a mathamatical proof for this approach, refer here.

Lets understand the approach with the same example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

At step 2, we achieved the maximum area.

Code:

Implemented in C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        // Initializing maximum Area as zero
        // Initializing the two pointers as beginning and end.
        int maxArea=0,i=0,j=height.size()-1;

        while(i<j){ //work till area is positive
            // Calculate area for each pair
            maxArea = max(maxArea, min(height[i], height[j])*(j-i));
            if(height[i]<=height[j]) i++; // if left pointer is small
            else j--; // if right pointer is small
        }
        return maxArea; //returning maximum area
    }
};

The time complexity of this approach is O(n) which is accepted. This technique of using two pointers is called Two Pointer Technique or Sliding Window Technique, click here for more questions.