LeetCode: Container With Most Water Solution

Approach

The point here is to prove why when

we move to the right

By contradiction, if we move

to the left instead:

• horizontal length will reduce whatever
• if
  h[j-1] < h[i]
  -> area will be
  h[j-1] * horizontal length
  -> smaller than previous
• if
  h[j-1] > h[i]
  -> area will be
  h[i] * horizontal length
  -> smaller than previous

So there is no way moving

to the left will produce larger area

Implementation

1/**
2 * @param {number[]} height
3 * @return {number}
4 */
5var maxArea = function (height) {
6  let i = 0
7  let j = height.length - 1
8  let max = -Infinity
9  while (i != j) {
10    max = Math.max(max, Math.min(height[i], height[j]) * Math.abs(i - j))
11    if (height[i] > height[j]) {
12      j--
13    } else {
14      i++
15    }
16  }
17  return max
18}