# Container With Most Water

## Container's area

`area = heigt * width`

A container in this problem has two heights. According to Liebig's law of the minimum, the smaller height should be selected to calculate the area.

```
i and j is the index of the input
function area(i, j)
return MIN(height[i], height[j]) * ABS(i - j)
```

## Maximizing the area

Maybe, sometimes, I'd to brute force every pair of `i`

and `j`

.

```
max = MIN_VALUE
foreach i in heights
foreach j in heights
max = MAX(area(i,j), max)
```

### Using brain

#### Needless comparing

Instead of brute force each `i`

and `j`

, we can choose the next `i`

or `j`

which may cause the area bigger.

take a look at `MIN(height[i], height[j]) * ABS(i - j)`

, when the enumeration is like

```
foreach i = 0 -> end
foreach j = end -> 0
max = MAX(area(i,j), max)
```

the `i`

and `j`

are getting closer, so the only factor is `MIN(height[i], height[j])`

.
Attempting to compare the `height`

s smaller than `MIN(height[i], height[j])`

are needless.

#### Redundant enumeration

After `i`

and `j`

meet each other, the rest of enumeration are redundant. so improved version should be like

```
foreach i = 0 -> end
foreach j = end -> i
max = MAX(area(i,j), max)
```

now, lets see what happens when `i`

moves to `i + 1`

and `j`

remains the same.

```
height[i] > height[j] and height[i + 1] < height[j]
MIN(height[i], height[j]) = height[j]
MIN(height[i + 1], height[j]) = height[i + 1]
area's height is getting smaller
height[i] > height[j] and height[i + 1] > height[j]
MIN(height[i], height[j]) = height[j]
MIN(height[i + 1], height[j]) = height[j]
area's height remains the same
height[i] < height[j] and height[i + 1] < height[j]
MIN(height[i], height[j]) = height[i]
MIN(height[i + 1], height[j]) = MIN(height[i], height[i + 1])
area's height is getting smaller
height[i] < height[j] and height[i + 1] > height[j]
MIN(height[i], height[j]) = height[i]
MIN(height[i + 1], height[j]) = height[j]
area's height is getting bigger
```

as you can see only `height[i] < height[j]`

, then `i`

moves to `i + 1`

might generate a bigger area.
this also applies to `j`

moves to `j - 1`

.

Now, our greedy code goes as following

```
i = 0
j = end
while i and j not meet
max = MAX(area(i,j), max)
if height[i] < height[j]
i = i + 1
if height[i] > height[j]
j = j - 1
```

### Source code *Read on Github*

```
1 public class Solution {
2 public int maxArea(int[] height) {
3
4 if(height.length <= 1) return 0;
5
6
7 int st = 0;
8 int ed = height.length - 1;
9
10
11 int max = Integer.MIN_VALUE;
12
13 while(st < ed){
14
15 int current = Math.min(height[st] , height[ed]) * (ed - st);
16
17 if(current > max) max = current;
18
19 if(height[st] <= height[ed]){
20 st++;
21 }else{
22 ed--;
23 }
24
25
26 }
27
28
29 return max;
30
31 }
32 }
```