Leetcode – 11 – Container With Most Water

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.

Description:

In this problem we have to check the point at which the container will hold the maximum of the water from the left end to the right end.

Brute Force Solution: (check for all possible left and right combinations)

We can try all the combinations of the left and right points to determine the maximum point. But this will take O(n2) since we are checking for each of left and right combinations. left and right being the index and index + 1 upto the length of the array.

Time Complexity: O(n2)

Efficient solution: (Using two pointer from left(0) and right(n-1))

The efficient solution can be to have two pointers pointing to left and right.

  • The area formed by left and right pointer is calculated.
  • If height of left is smaller than right, the left pointer is increased, otherwise we will decrease the right pointer.
  • The maximum area is saved on each iteration1

Code:

public class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int max = 0;
        if(height != null &&  n >= 2){
            int left = 0;
            int right=n-1;
            
            while(left < right){
                int currentArea = Math.min(height[left], height[right]) * (right - left);
                max = Math.max(max, currentArea);
                if(height[left] < height[right]){
                    left++;
                }
                else{
                    right--;
                }
            }
            
        }
        return max;
    }
}

Time Complexity: O(n)

  • Loop through the content of the array – O(n)

Space Complexity: O(1)

  • We will store the values in the max – O(1)

Available Test Cases: 45

  • handle overflow cases

 Github:

Leetcode_11_Container_With_Most_Water

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: