LeetCode: Container With Most Water Solution

Approach

The point here is to prove why when h[i] < h[j] we move i to the right

By contradiction, if we move j 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 j 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}

Comments

Loading comments...