[Leetcode][11. Container With Most Water] 2 Approaches: BF and Two Pointers with Image Explaination | Code Commented

By Long Luo

This article is the solution of Problem 11. Container With Most Water.

Here shows 2 Approaches to slove this problem, Brute Force and Two Pointers.

Intuition

Problem 11

Suppose two pointers ii, jj, the heights of the vertical lines are h[i]h[i], h[j]h[j], and the area in this state is S(i,j)S(i, j).
As we all known, the container is determined by the short line, the area formula can be easily obtained:

S(i,j)=min(h[i],h[j])×(ji)S(i, j)= min(h[i], h[j]) \times (j - i)

Brute Froce

It’s easy to use the brute force approach, the total states is C(n,2)=n×(n1)/2C(n, 2)= n \times (n - 1) / 2, we have to enumerate all these states to get the max area.

The time complexity is O(n2)O(n^2), exceed the time limit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// BF time: O(n^2) space: O(1)
// TimeOut
public static int maxArea_bf(int[] height) {
int len = height.length;
int max = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
int area = Math.min(height[i], height[j]) * (j - i);
max = Math.max(max, area);
}
}

return max;
}

Analysis

  • Time Complexity: O(n2)O(n^2)
  • Space Complexity: O(1)O(1)

Two Pointers

In each state S(i,j)S(i, j), no matter whether the left line or right line moves to the middle, it will cause less wide to width1width - 1:

  • Move the short line, the short line min(h[i],h[j])min(h[i], h[j]) of the container may hold more water, the area may increase.
  • Move the long line, the short line min(h[i],h[j])min(h[i], h[j]) of the container will remain the same or less, so the area will definitely become less.

Therefore, we can use two pointers to the left and right line of the container. We move the short line in each round, update the max area until the two pointers met each other as the below pictures show.

Problem 11 1

Problem 11 2

Problem 11 3

Proof

Assuming that h[i]<h[j]h[i] < h[j] under the state S(i,j)S(i, j), move the short line to S(i+1,j)S(i + 1, j), which means that we eliminate S(i,j1),S(i,j2),...,S(i,i+1)S(i, j - 1), S(i, j - 2), ... , S(i, i + 1) states. The area of all eliminated states must be smaller than the current area:

  1. Short line height: same or less than S(i,j)S(i, j) (h[i]\le h[i]);
  2. Width: less than S(i,j)S(i, j).

Therefore, each round moves the short line, and all the eliminated states will not cause the loss of the maximum area.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Two Pointers time: O(n) space: O(1)
public static int maxArea_tp(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int max = Math.min(height[left], height[right]) * (right - left);
while (left < right) {
// Move the shorter lines each time
if (height[left] <= height[right]) {
left++;
} else {
right--;
}

// update the max area
max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
}

return max;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗