# Container With Most Water

ID: 11; medium

## Solution 1 (Java)

``````class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
int w = j - i;
int h = Math.min(height[i], height[j]);
maxArea = Math.max(maxArea, w * h);
}
}
return maxArea;
}
}``````

This is the brute force solution that iterates every possible areas that can be formed by the heights. This will not pass the LeetCode time constraint despite of its correctness.

## Solution 2 (Java)

``````class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int w = right - left;
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, w * h);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}``````

This is the two-pointer approach.

The best intuition for this approach I have come across is the following: To ensure the maximum area, there are two things in consideration: height and width. To start with, we have already had the largest width (by starting `left = 0` and `right = height.length - 1`. When we consider `left` and `right`, if the `left` is shorter, we move the `left` pointer to the right because the current area is already the maximum area that can be formed by the `left` height. Namely, any movement of the `right` pointer to left would decrease the area. The same is for the other case for the `right` pointer.

You may also do a rigorous proof such as proof by contradiction.

TL;DR: Each step we are can only be improving the situation (not making it worse, i.e., decreasing the area). This is similar to the idea of proving a greedy algorithm.

Last updated