Problem Statement: 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.
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:
C++ 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;
}
Output:
Maximum amount of water is: 6
TIME COMPLEXITY: O(n^2)
SPACE COMPLEXITY: O(1) no extra space used
Java Code
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));
}
}
Output:
Maximum amount of water is: 6
TIME COMPLEXITY: O(n^2)
SPACE COMPLEXITY: O(1) no extra space used
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:
C++ 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;
}
Output:
Maximum amount of water is: 6
TIME COMPLEXITY: O(n)
SPACE COMPLEXITY: O(1)
Java Code
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));
}
}
Output:
Maximum amount of water is: 6
TIME COMPLEXITY: O(n)
SPACE COMPLEXITY: O(1)
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