Reference: LeetCode
Difficulty: Medium

My Post: [Java] Two Pointers with Explanation (easy-understand)

Problem

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.

LeetCode

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

Example: 

1
2
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Analysis

Brute-Force

Try every container.

1
2
3
4
5
6
7
8
9
10
public int maxArea(int[] height) {
  int n = height.length;
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
    }
  }
  return max;
}

Time: $O(N^2)$
Space: $O(1)$

Two Pointers

We have two pointers lo and hi that start from two ends. Each time we update the one with smaller height.

Why?

It is kind of pruning unnecessary cases. If height[lo] < height[hi], we move lo because we know that the areas in which lo is the left bar ([lo, lo + 1],[lo, lo + 2], …, [lo, hi - 1]) must be less than the area in [lo, hi] that we just considered. So next time we should not consider lo as the left end anymore.

For example, all the areas (AB, AC, AD, …, AH) are less than AI.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxArea(int[] height) {
  // assume n >= 2
  int n = height.length;
  int lo = 0, hi = n - 1;
  int max = Integer.MIN_VALUE;
  while (lo < hi) {
    int water = (hi - lo) * Math.min(height[lo], height[hi]);
    max = Math.max(max, water);
    if (height[lo] < height[hi]) ++lo;
    else --hi;
  }
  return max;
}

Time: $O(N)$
Space: $O(1)$