11. Container With Most Water

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.

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

Solution:

Greedy Algorithm.

If we look at the simple brute force approach, where we choose one point at a time and calculate all the possible areas with other points on the right, it is easy to make a observation that we are narrowing down the horizontal distance.

Greedy Algorithm can help us skip some of the conditions. It is base on a fact that the area between two columns are determined by the shorter one.

Let’s say we have pointer l and r at the begin and end of a distance, and the area is area(l, r), how should we narrow down the distance?

If height[l] < height[r], we know that the height of the area will never be greater than height[l] if we keep l. Now if we get rid of r, the area can only get smaller since the distance is shorter, and the height is at most height[l].

Here we conclude rule NO.1: Get rid of the smaller one.

What if height[l] == height[r]? It is safe to get rid of both. We do not need any of them to constrain the max height of the rest points.

/**
 * @param {number[]} height
 * @return {number}
 */
let maxArea = function (height) {
  let max = 0;
  for (let l = 0, r = height.length - 1; l < r; l++, r--) {
    max = Math.max(max, (r - l) * Math.min(height[l], height[r]));
    if (height[l] < height[r]) {
      r++;
    } else {
      l--;
    }
  }
  return max;
};

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆