5
\$\begingroup\$

The task is taken from leetcode

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.

My first solution:

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = height => {
  let max = 0;
  height.forEach((hL, i) => {
    height.slice(i + 1).forEach((hR, j) => {
      max = Math.max(max, Math.min(hL, hR) * (1 + j));
    });
  });
  return max;
};

My second solution:

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea2 = height => {
  let l = max = 0;
  let r = height.length - 1;
  while (l < r) {
    const area = Math.min(height[l], height[r]) * (r - l);
    if (height[l] > height[r]) {
      r--;      
    } else {
      l++;
    }
    max = Math.max(max, area);
  }
  return max;
};

Is it possible to solve it mathematically and make it faster?

\$\endgroup\$
  • \$\begingroup\$ Strictly speaking your code doesn't solve the task. It only finds the maximum area, but it does not say which of the lines form the container. The task says "find the lines". \$\endgroup\$ – Roland Illig May 16 at 6:28
  • \$\begingroup\$ I solved it consistently with the example they gave (See link in OP) @RolandIllig \$\endgroup\$ – thadeuszlay May 16 at 15:13
  • \$\begingroup\$ And I thought the tasks from leetcode had been peer reviewed and checked for accuracy. Apparently they aren't. :) \$\endgroup\$ – Roland Illig May 16 at 19:23
1
\$\begingroup\$

Is it possible to solve it mathematically and make it faster?

Not faster than the second solution, which is \$O(n)\$, making a single pass over the input. It's easy to see that it's not possible to find the correct answer without inspecting every element. For example, if two values are not inspected, then one could pick arbitrarily high values for them to make them produce the maximum area.

I have some style comments about the second solution:

  • I dislike the variable name l because in some fonts it can be confused with | or 1.
  • I would rename l to left and r to right for natural clarity. Still simple enough.
  • For symmetry with the while (l < r), I would rewrite the if in the loop body to be if (height[l] < height[r]), as I feel it would facilitate understanding of the logic.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.