## Problem Statement

You are given an array $height[n]$ of integers of size `n`

, where each value represents a coordinate position $(i, height[i])$. `n`

vertical lines are drawn such that the endpoints of line `i`

are at $(i, 0)$ and $(i, height[i])$. Find the container that is formed by two lines along with the x-axis, where the container contains the most water.

## Example

**Input – 1**

`height[] : [1, 5, 6, 3, 4, 2]`

**Output – 1**

`12`

**Explanation**

The area shown in the blue section is the maximum area.

`1`

and`4`

are distance`3`

apart.- Therefore, the size of the base =
`3`

. - Height of the container will be a minimum of $(5, 4)$ $= 4$
- Hence, The total area becomes $3 * 4$ $= 12$
**units**.

**Input – 2**

`height[] : [1, 1]`

**Output – 2**

`1`

**Explanation**

Since there are only two endpoints, the area becomes $1 * 1$ $= 1$.

## Constraints

```
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
```

## Algorithm – 1 : Naive Approach – Using Nested Loops

### Intuition

The most basic and straightforward approach for a container with the most water is to check all the possible pairs of boundaries and find out a team that has a maximum area.

### Algorithm

- Initialize a variable
**maxArea**to track the current maximum area. - Run a nested loop, the outer loop from $i = 0$ to end $(n-1)$.
- While the inner loop runs from $i+1$ to end $(n-1)$ with loop counter
`j`

. - Find the area for every pair of boundaries
`i`

and`j`

, and store the area in the variable**maxArea**, where**maxArea**= $(j -i)$*$min(height[i], height[j])$. Update the variable maxArea, if the current area is greater than the maxArea. - Return the maxArea.

### Code Implementation

**Code in C++ :**

```
#include <iostream>
using namespace std;
int maxContainer(int arr[], int n)
{
int maxArea = 0;
```*// Find the area for every pair of boundaries i and j*
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
*// Calculate the area*
*// and update the variable maxArea, if greater*
maxArea = max(min(arr[j], arr[i]) * (j - i), maxArea);
}
}
return maxArea;
}
*// Driver code*
int main()
{
int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int height2[] = { 1, 1 };
*// Call the function for the first array*
int len1 = sizeof(height) / sizeof(height[0]);
cout << maxContainer(height, len1);
*// Call the function for the second array*
int len2 = sizeof(height2) / sizeof(height2[0]);
cout << endl << maxContainer(height2, len2);
}

**Code in Java :**

*// Java code for Max*
*// Water Container*
import java.io.*;
class Main{
public static int maxContainer(int[] arr){
int maxArea = 0;
*// Find the area for every pair of boundaries i and j*
for(int i = 0; i < arr.length; i++){
for(int j = i + 1; j < arr.length; j++){
*// Calculate the area*
*// and update the variable maxArea, if greater*
maxArea = Math.max(maxArea, Math.min(arr[i], arr[j]) * (j - i));
}
}
return maxArea;
}
*// Driver code*
public static void main(String[] args)
{
int height[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
int height2[] = { 1, 1 };
*// Call the function for the first array*
System.out.println(maxContainer(height));
*// Call the function for the second array*
System.out.println(maxContainer(height2));
}
}

**Code in Python :**

*# Python code for Max*
*# Water Container*
def maxContainer(arr, Len) :
maxArea = 0
*# Find the area for every pair of boundaries i and j*
for i in range(Len) :
for j in range(i + 1, Len) :
*# Calculate the area*
*# and update the variable maxArea, if greater*
maxArea = max(maxArea, min(arr[j], arr[i]) * (j - i))
return maxArea
*# Driver code*
height = [ 1, 8, 6, 2, 5, 4, 8, 3, 7 ]
height2 = [ 1, 1 ]
len1 = len(height)
*# Call the function for the first array*
print(maxContainer(height, len1))
len2 = len(height2)
*# Call the function for the second array*
print(maxContainer(height2, len2))

**Output :**

```
49
1
```

**Time Complexity :**

The time complexity is $O(n^2)$. Since two nested loops traverse the array.

**Space Complexity :**

The space complexity is $O(1)$. Since no extra space is used in the solution of the container with the most water.

## Algorithm – 2 : Efficient Approach – Using Two Pointers

### Intuition

We take two pointers, one at the start and one at the end of the array, and we keep track of the maximum area between the lines in a variable **maxArea**. At each step, we calculate the area formed by the two pointers, update the maximum area, and move the pointer pointing to the shorter line by one to the opposite end.

Check the below illustration of two pointer approach to solving container with most water problem :

### Algorithm

- Initialize a variable maxArea to track the current maximum area of a container with the most water.
- Keep two indices, $i$ and $j$ initialized at
`0`

and $n-1$, respectively. - Run a loop until the left index
`i`

is less than the right index`j`

. - Calculate the area formed between indices
`i`

and`j`

, where**area**$= Math.min(height[i], height[j]) * (j – i))$ and update the**maxArea**. - If the value at $height[i]$ is lesser than $height[j]$ then move index
`i`

by one right. Else move index`j`

by one left. - Return the maxArea.

### Code Implementation

**Code in C++ :**

*// C++ code for Max*
*// Water Container*
#include<iostream>
using namespace std;
int maxContainer(int arr[], int n){
int i = 0;
int j = n -1;
int maxArea = 0;
while (i < j){
*// Calculate the area*
*// and update the variable maxArea, if greater*
maxArea = max(maxArea, min(arr[i], arr[j]) * (j - i));
if (arr[i] < arr[j])
i += 1;
else
j -= 1;
}
return maxArea;
}
*// Driver code*
int main()
{
int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int height2[] = { 1, 1 };
int len1 = sizeof(height) / sizeof(height[0]);
*// Call the function for first array*
cout << maxContainer(height, len1);
int len2 = sizeof(height2) / sizeof(height2[0]);
*// Call the function for second array*
cout << endl << maxContainer(height2, len2);
}

**Code in Java :**

*// Java code for Max*
*// Water Container*
import java.util.*;
class Area{
public static int maxContainer(int arr[]){
int i = 0;
int j = arr.length - 1;
int maxArea = 0;
while (i < j){
*// Calculate the area*
*// and update the variable maxArea, if greater*
maxArea = Math.max(maxArea,
Math.min(arr[i], arr[j]) * (j - i));
if (arr[i] < arr[j])
i += 1;
else
j -= 1;
}
return maxArea;
}
public static void main(String[] args)
{
int height[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
int height2[] = { 1, 1 };
*// Call the function for the first array*
System.out.println(maxContainer(height));
*// Call the function for the second array*
System.out.println(maxContainer(height2));
}
}

**Code in Python :**

*# Python3 code for Max*
*# Water Container*
def maxContainer(arr):
i = 0
j = len(arr) -1
maxArea = 0
while i < j:
*# Calculate the area*
*# and update the variable maxArea, if greater*
maxArea = max(maxArea, min(arr[i], arr[j]) * (j - i))
if arr[i] < arr[j]:
i += 1
else:
j -= 1
return maxArea
*# Driver code*
height = [ 1, 8, 6, 2, 5, 4, 8, 3, 7 ]
height2 = [ 1, 1 ]
*# Call the function for the first array*
print(maxContainer(height))
*# Call the function for the second array*
print(maxContainer(height2))

**Output :**

```
49
1
```

**Time Complexity :**

The time complexity is $O(n)$. Since only one traversal of the array is required.

**Space Complexity :**

The space complexity is $O(1)$. Since no extra space is used in the solution of the container with the most water.

## Conclusion

- We have given an integer array $height[n]$ of length n, where each value refers to a coordinate position $(i, height[i])$.
- We have to find the two lines that form a container along with the x-axis, such that the container contains the most water.
- For eg, If the array is $[1,8,6,2,5,4,8,3,7]$, the
**size of the base**$= 7$, Height of the container will be`7`

and the area becomes $7*7 = 49$ units. - The naive approach takes $O(n^2)$ time complexity as two loops were used, and $O(1)$ space complexity because no extra space is used.
- On the other hand, the efficient approach for a container with most water is using the
**Two-pointer Technique**. It takes $O(n)$ time complexity and $O(1)$ as space complexity. - We initialize a variable
**maxArea**in both approaches to track the current maximum area.

## FAQs

Q. **How can the area between two points be calculated ?**

A. The length is the distance between the two endpoints, and the minimum of the two heights is going to be the height because each consecutive block’s width is considered to be `1`

. Hence, **area** $= Math.min(height[i], height[j]) * (j – i))$.

Q. **What is the most efficient approach to solve this problem ?**

A. The most efficient approach for a container with the most water is using the Two-pointer Technique because it takes $O(n)$ time complexity and $O(1)$ as space complexity.

Q. **Similar Coding questions to practice?**

A. Refer to Trapping Rain Water

- Refer Triplet with Zero Sum