# 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 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)