Container with most water

Problem Statement:  Given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

Examples:

Input: nums = [1,4,2,3]
Output: 6

Explanation: At i = 1 and i=3 heights are 4 and 3, therefore the maximum amount of water can be stored there. To calculate any amount of water between 2 vertical lines it is the horizontal distance between them multiplied by the minimum of those 2 lines. So in the best case, the max distance between i=1 and i=3 is 2, and the minimum of 4 and 3 is 3, so total water is 2*3=6.

Example 2:
Input: nums = [1,8,6,2,5,4,8,3,7]
Output: 49
Here maximum water can be contained between i=1 and i=8

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach:  

To get the maximum water, we can calculate using 2 loops. At each iteration, we require a distance between 2 lines and the minimum of those lines. So we start with i= 0 and j=i+1. Then calculate max at nums[i] for every other j. We keep a global max and when both loops are done, the value of the max is the answer.

In the above example , we start from i=0 , j starts from 1, for nums[i]=1 and nums[j] = 4, max is (1-0)*min(4,1) = 1, we the loop j till 3. Next iteration I starts at 1, for j = 2,3 and so on.

Code:

#include<bits/stdc++.h>
using namespace std;

int maxArea(vector<int> &nums)
{
    int mx = INT_MIN;
	for(int i = 0; i < nums.size(); i++){
		for(int j = i + 1; j < nums.size(); j++){
			int water = (j-i)*min(nums[i], nums[j]);
			mx = max(mx,water);
		}
	}
    return mx;
}

int main() {
    vector<int> nums {1, 4, 2, 3};
  
    cout << "Maximum amount of water is: " << maxArea(nums);
  
    return 0;
}

Maximum amount of water is: 6

import java.util.*;

class TUF{
    static int maxArea(int nums[]) {
	   int mx = Integer.MIN_VALUE;
    	for(int i = 0; i < nums.length; i++){
    		for(int j = i + 1; j < nums.length; j++){
    			int water = (j-i)* Math.min(nums[i], nums[j]);
    			mx = Math.max(mx, water);
    		}
    	}
        return mx;
	}
    public static void main(String args[])
    {
    	int nums[] = {1, 4, 2, 3};
    	
    	System.out.println("Maximum amount of water is: " + maxArea(nums));
    }
}

Maximum amount of water is: 6

OPTIMAL APPROACH:

We can improve the above approach by using 2 pointers. The basic equation is                

 (j-i)*min(nums[j],nums[i]).  So we start by maximizing j-i , that is , start with i=0 and j= nums.size()-1. 

There is a global max where we keep track of water at each site.

Now that i and j are maximum , we can focus on nums[i] and nums[j] , to check if we can further improve the result . Since we are taking the min(nums[i], nums[j]), we have to maximize the minimum element . so if nums[i] is minimum i++ or else j – – .

here water = (3-0)*(1) = 3
mx = 3 
Since nums[i] is min we do i++

Next Iteration,

here water = (3-1)*(3) = 6
mx = max(mx, water) 
Since nums[j] is min we do j - -

Next Iteration,

here water = (2-1)*(2) = 2
mx = max(mx, water)  = still 6
Since nums[j] is min we do j - -
Now i and j  are same , we stop.

Code:

#include<bits/stdc++.h>
using namespace std;

int maxArea(vector<int> &nums)
{
    int i = 0,j = nums.size() - 1, mx = INT_MIN;
	while(i < j)
	{
		int water = (j-i)*min(nums[i],nums[j]);
		mx = max(mx,water);
		if(nums[i] < nums[j])
		    i++;
		else
		    j--;
	}
	
	return mx;
}

int main() {
    vector<int> nums {1, 4, 2, 3};
  
    cout << "Maximum amount of water is: " << maxArea(nums);
  
    return 0;
}

Maximum amount of water is: 6

import java.util.*;

class TUF{
    static int maxArea(int nums[]) {
        
        int i = 0,j = nums.length - 1, mx = Integer.MIN_VALUE;
    	while(i < j)
    	{
    		int water = (j-i)* Math.min(nums[i],nums[j]);
    		mx = Math.max(mx,water);
    		if(nums[i] < nums[j])
    		    i++;
    		else
    		    j--;
    	}
	
	    return mx;
	}
    public static void main(String args[])
    {
    	int nums[] = {1, 4, 2, 3};
    	
    	System.out.println("Maximum amount of water is: " + maxArea(nums));
    }
}

Maximum amount of water is: 6

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article