Given *n* non-negative integers *a _{1}*,

*a*, …,

_{2}*a*, where each represents a point at coordinate (

_{n }*i*,

*a*).

_{i}*n*vertical lines are drawn such that the two endpoints of line

*i*is at (

*i*,

*a*) and (

_{i}*i*, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example 1: Input:[1,8,6,2,5,4,8,3,7]Output:49Explanation:

Constrains: 0 < sizeof(heightArray) <= 10^5

Question Link: **Container With Most Water**

## Solution:

The first **brute force** way to approach this problem is to start from each line *i *and check its capacity with all lines *j *such that *i < j < n* which is pretty simple.

**Code:**

Implemented in C++

```
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea=0; // Initializing maximum area as 0
for(int i=0; i<height.size(); i++){
for(int j=i+1; j<height.size();j++){
// Going through all pairs (i,j) for maximum container area.
maxArea = max(maxArea, min(height[i], height[j])*(j-i));
}
}
return maxArea;
}
};
```

But the time complexity of this approach is O(n^2) which is not accepted.

#### Better Approach

The main catch in this question is to find the maximum area which can be caused due to two factors:

**Bigger Width****Bigger Height**

Lets firstly maximize the width by taking the two **extreme ends** of the input array i.e. * 0 and n-1* as two pointers and then continue to decrease each end along with calculating area for each case. But question is which end should we decrease?

There are two possibilities:

- Both pointers’ heights are same
- They have different heights

If we switch from a pointer having more height, the we are losing a potential pair which can have better area while decreasing the pointer having less height will not cause any trouble. So, we should **decrease the pointer having less height**. This is a greedy approach, for a **mathamatical proof** for this approach, refer here.

Lets understand the approach with the same example:

Input:[1,8,6,2,5,4,8,3,7]Output:49

At **step 2**, we achieved the maximum area.

**Code:**

Implemented in C++

```
class Solution {
public:
int maxArea(vector<int>& height) {
// Initializing maximum Area as zero
// Initializing the two pointers as beginning and end.
int maxArea=0,i=0,j=height.size()-1;
while(i<j){ //work till area is positive
// Calculate area for each pair
maxArea = max(maxArea, min(height[i], height[j])*(j-i));
if(height[i]<=height[j]) i++; // if left pointer is small
else j--; // if right pointer is small
}
return maxArea; //returning maximum area
}
};
```

The time complexity of this approach is **O(n)** which is accepted. This technique of using two pointers is called **Two Pointer Technique or Sliding Window Technique**, click here for more questions.