## (Container With Most Water)

Given $n$ non-negative integers $a_{1}, a_{2}, \dots, a_{n}$, where each represents a point at coordinate $(i, a_{i})$. $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, a_{i})$ 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.

Thoughts:
Mathematically, the solution to the problem is given by $\arg\max_{i. We take a "closing into the center" approach. Starting with $i = 0, j = n - 1$. We initialize the largest area as $\min(a_{i},a_{j})\cdot(n-1)$. Next, we try want to move. We have two options: increase $i$ or decrease $j$. Let me state a lemma first:
$\forall i if $a_{i} < a_{j}$.
Proof:

• If $a_{k} \leq a_{i}$, then $\text{Area}(i,k) = a_{k}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j)$.
• If $a_{k} > a_{i}$, then $\text{Area}(i,k) = a_{i}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j)$.

This tells us if $a_{i} < a_{j}$ and we increase $i$ by 1, we can rule out the $\text{Area}(i,i+1)$ since it must be smaller than $\text{Area}(i,j)$. Similarly, we can decrease $j$ by 1 if $a_{i} \leq a_{j}$. This gives us the iterative structure of the program. We stop until $i$ meets $j$. Therefore this is a $O(n)$ algorithm.

Code (C++):

class Solution {
public:
int maxArea(vector<int> &height) {
int i =0;
int j = height.size() - 1;
int best = min(height[i], height[j]) * (j-i);
if(height[i] < height[j])
i++;
else
j--;

while(i < j) {
int area = min(height[i], height[j]) * (j-i);
if(area  > best)
best = area;

if(height[i] < height[j])
i++;
else
j--;
}
return best;
}
};

Code (Java):
public class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int best = Math.min(height[i], height[j]) * (j-i);

if(height[i] < height[j])
i++;
else
j--;

while(i < j) {
int area = Math.min(height[i], height[j]) * (j-i);
if(area > best)
best = area;

if(height[i] < height[j])
i++;
else
j--;
}

return best;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de98cd473a', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de98cd4769',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de98cd476b',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});