Container with most water

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?

• 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". – Roland Illig May 16 at 6:28
• I solved it consistently with the example they gave (See link in OP) @RolandIllig – thadeuszlay May 16 at 15:13
• And I thought the tasks from leetcode had been peer reviewed and checked for accuracy. Apparently they aren't. :) – Roland Illig May 16 at 19:23

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.