11.container-with-most-water.md

11. Container With Most Water

The area = min(h[i], h[j]) * (j - i), the amount of water is limited by the shorter wall.

  |
  |~~~~~~~|
| | | | | | | |
----------------
  i       j

The max area comes from the two choices:

1. The widest
2. The highest

Idea!! We start the widest choice at the first and the last position, move the two pointers left -> ... <- right , all other possible choices are less wide (width minus 1), to get a better solution, we need to choose a higher height. So we drop (move) the pointer with the lower height for further consideration which doesn't support higher height.

• 只需要移动 height[left] 和 height[right] 中较矮的一个板子即可，这样才有使总面积增大的可能。否则移动较高的板子，不会使结果变得更好，因为最终的容积是由较矮的那根柱子决定的。
• 因為容器能裝多少水是由兩根柱子中較矮的那一根決定的，如果我們移動較高的那根柱子，那麼容器的高度限制並沒有改變，反而會讓寬度縮小，這樣就很難得到更大的容積。所以我們選擇移動較矮的那根柱子，才有可能在縮小寬度的同時，提升高度的限制，從而有機會找到更大的容量。

Detail Explanation

How to move the two pointer? Which pointer should we move first?

[... 999 ..... 6 ...]
      L ->  <- R

Suppose left = 999, right is 6, and width is 5, let's consider the result of moving left and right pointer:

Case 1. We move higher height left pointer, we will meet the possible height in next round:

• 2000 (higher height)
• 999 (same height)
• 8 (lower height) the width becomes smaller which is 4, the possible area is 4 * min(2000, 6) / 4 * min(999, 6) / 4 * min(8, 6), respectively, all possible height leads to smaller area. No matter what the next height is, the area guarantees to be smaller than 5 * min(999, 6).

Case 2. If we move smaller height right pointer, we might find the higher height later even if the width becomes smaller, it might be possible to find the larger area. If we don't meet higher height, then the current result 5 * min(999, 6) would be the max area.

So, we conclude that we can move the pointer with the shorter height.

How about the equal height? We can move either one, neither (left + 1, right) or (left, right - 1) can be potential max area because the width is smaller and the area obtained is necessarily smaller than (left, right). Or we can move both, it doesn't matter.

// Move left if the left == right
i: 0,1,2,3,4,5,6,7,8
v: 1,8,6,2,5,4,8,3,7
   L               R, min(1,7)*8, 8
     L             R, min(8,7)*7, 49
     L           R,   min(8,3)*6, 18
     L         R      min(8,8)*5, 40
       L       R      min(6,8)*4, 24
         L     R      min(2,8)*3, 6
           L   R      min(5,8)*2, 10
             L R      min(4,8)*1, 4

// Move right if the left == right
     L       R        min(8,4)*4, 16
     L     R          min(8,5)*3, 15
     L   R            min(8,2)*2, 4
     L R              min(8,6)*1, 6   

def maxArea(self, height: List[int]) -> int:
    max_area = 0
    left, right = 0, len(height) - 1
    while left < right:
        current_area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, current_area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var maxAmount = 0
    while (left < right) {
        val lowerHeight = minOf(height[left], height[right])
        val width = right - left
        maxAmount = maxOf(maxAmount, lowerHeight * width)

        // It's fine for `height[left] <= height[right]``
        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }

        // Or we can move both when the height is equal.
        // } else if (height[left] == height[right]) {
        //     left++
        //     right--
        // }
    }
    return maxAmount
}

• Time Complexity: O(n), we only traverse the array once.
• Space Complexity: O(1), we don't use any extra space.

We move the left or left pointer when the height of two sides are equal, here is some test cases:

8 6 7 8
l     r = 8 * 3 ^^
  l   r = 6 * 2
    l r = 7 * 1

8 6 7 8
l     r = 8 * 3 ^^
l   r   = 7 * 2
l r     = 6 * 1

8 6 9 8
l     r = 8 * 3 ^^
  l   r = 6 * 2
    l r = 8 * 1

8 6 9 8
l     r = 8 * 3 ^^
l   r   = 8 * 2
  l r   = 6 * 1

4 6 7 4
l     r = 4 * 3 ^^
  l   r = 4 * 2
  l r   = 6 * 1

4 6 7 4
l     r = 4 * 3 ^^
l   r   = 4 * 2
  l r   = 6 * 1