2017-09-19 @sunderls

https://leetcode.com/problems/container-with-most-water/description/

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The brutal force solution cost us *O(n ^{2})*, with a nested loop.

```
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
var max = 0;
var i = 0;
var j = 0;
var total = height.length;
if (total < 2) {
return 0;
}
for (;i <= total - 2; i++) {
for (j = i + 1;j <= total - 1; j++) {
max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
}
}
return max;
};
```

well, of course, time limit Exceeded!

see if we can cut down some unnecessary comparison.

**if ai is the largest container, what whould it be?**

```
1. for i to 0
if ai >= ai+1
then ai+1 is not candidate, because ai has larger values both in x and y
if ai < ai+1
then we should calcuate the area
2. for i to n
if ai >= ai-1
then ai-1 is not candidate, same as above
if ai < ai-1
then we should calcuate the area
```

and then ........... I stuck here!!!

so, each pillar could be the left pillar or the right one right? according to above algorithm, we can safely flag the pillars, not for both, but for only one side?

so we do comparison and get two arrays of possible pillars.

- possible right pillars are a downward line
- possible left pillars are a upward line

** does this improve ?**

seems so, but I need to prove that later

**how can we derive these two arrays?**

like a toothed saw, we have to keep every tooth and compare like for possible right pillars

```
currentTooth = 0
couldBeRightPillar[]
for i from 0 to n
couldBeRightPillar[i] = true
k = i
while a[k--] < a[i] && k >= currentTooth
couldBeRightPillar[k] = false
# collect from couldBeRightPillar[]
```

do the reverse version to derive possible left pillars

```
var maxArea = function(height) {
var total = height.length;
if (total < 2) {
return 0;
}
var couldBeRightPillars = [];
var couldBeLeftPillars = [];
var currentTooth = 0;
var i = 0, k = 0;
for (var i = 0; i < total; i++) {
couldBeRightPillars[i] = true;
k = i - 1;
while (k >= currentTooth && height[i] >= height[k]) {
couldBeRightPillars[k] = false;
k -= 1;
}
}
currentTooth = i = total - 1;
k = 0;
for (; i > -1; i--) {
couldBeLeftPillars[i] = true;
k = i + 1;
while (k <= currentTooth && height[i] >= height[k]) {
couldBeLeftPillars[k] = false;
k += 1;
}
}
// extrac possible pillars
var possibleLeftPillars = [];
var possibleRightPillars = [];
for (i = 0; i < total; i++) {
if (couldBeRightPillars[i]) {
possibleRightPillars.push(i);
}
if (couldBeLeftPillars[i]) {
possibleLeftPillars.push(i);
}
}
var max = 0;
// now calculate the result
for (i = 0; i < total - 1; i++) {
for (k = i + 1; k < total; k++) {
max = Math.max(max, (k - i) * Math.min(height[i], height[k]));
}
}
return max;
};
```

**but still time exceeded**

wait a minute, for a dot i to be a left pillar, with corresponding right pillar k

- a[i] < a[k]: then for j > k, a[j] must be smaller than a[k];
- a[i] > a[k]: then for j < i, a[i] must be smaller than a[i];

right pillars must be on the right, left pillars must be on the left, from these 2 assumptions, maybe we can caculate at same time, from both ends!!

```
var maxArea = function(height) {
var i = 0;
var j = height.length - 1;
var max = 0;
while (i < j) {
// if left one is smaller
// then the container for left is at its max
// we can safely skip i because this is most for it
// * i and j + 1 may be larger by it is already check in j + 1 turn
max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
if (height[i] < height[j]) {
i += 1;
// same for the short right pillar
} else if (height[i] > height[j]) {
j -= 1;
// if they are the same, then both are at there possible max
} else {
i += 1;
j -= 1;
}
}
return max;
};
```

**accepted, ranking bottom 40% though**

so I overthought the problem. the key here is that *right pillar stays on the right and left to the left*, which leads us to starting from both ends

about complexity: every number is compared only one time, so it should be O(n), right?

thing is that when we can skip downward slopes on the left and upward slope on the right!

```
var maxArea = function(height) {
var i = 0;
var j = height.length - 1;
var tmp = 0;
var max = 0;
while (i < j) {
// if left one is smaller
// then the container for left is at its max
// we can safely skip i because this is most for it
// * i and j + 1 may be larger by it is already check in j + 1 turn
max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
tmp = Math.min(height[i], height[j]);
if (height[i] < height[j]) {
i += 1;
while (i < j && height[i] <= tmp) {
i += 1;
}
// same for the short right pillar
} else if (height[i] > height[j]) {
j -= 1;
while (j > i && height[j] <= tmp) {
j -= 1;
}
// if they are the same, then both are at there possible max
} else {
i += 1;
j -= 1;
}
}
return max;
};
```

but only ranks up a little. what's there to be improved?!!

the problem seems to be that for height[i] === height[j], we can cut down this condition, merge it to height[i] <= height[j]

```
var maxArea = function(height) {
var i = 0;
var j = height.length - 1;
var tmp = 0;
var max = 0;
while (i < j) {
// if left one is smaller
// then the container for left is at its max
// we can safely skip i because this is most for it
// * i and j + 1 may be larger by it is already check in j + 1 turn
tmp = Math.min(height[i], height[j]);
max = Math.max(max, (j - i) * tmp);
if (height[i] <= height[j]) {
i += 1;
while (i < j && height[i] <= tmp) {
i += 1;
}
// same for the short right pillar
} else {
j -= 1;
while (j > i && height[j] <= tmp) {
j -= 1;
}
}
}
return max;
};
```

now it ranks top thirty, improved a lot.