LeetCode - 11. Container with Most Water

[LeetCode] 11. Container with Most Water

LeetCode 11번 문제를 풀어보았다.. Link

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Intuition

물의 양을 최대로 하는 두개의 Line을 고르는 문제로, Brute force를 사용하면 간단하게 해결이 가능하다 (모든 쌍의 Line에 대해서 저장할 수 있는 물의 양을 비교).

하지만 이는 \(O(n^2)\)의 시간복잡도를 가지기 때문에 최적화방안을 찾아야한다.

Approach

기본적인 Brute Force Approach는 아래와 같다.

1. height[i]는 height의 i번째 성분을 의미한다.
2. max_water는 저장가능한 최대 물의 양이 저장되는 변수이다.
3. i=0부터, j=i+1부터 시작하여 반복되는 변수이다.
4. height[i]와 height[j]중 더 낮은 Line을 low라고 한다.
5. i와 j번째 Line이 저장할 수 있는 물의 양은 water=low * (j-i)이다.
6. water가 max_water보다 크면 max_water를 갱신한다.
7. j가 n이 될 때 까지 4~6을 반복한다.
8. i가 n-1이 될 때 까지 4~7을 반복한다.

이를 최적화하는 방법은 아래와 같다.

• Optimization의 3요소
  • Cost function: 시간복잡도
  • Decision variable: Height의 길이, 반복 횟수
  • Constraint
• 여기서 길이는 변경할 수 없기 때문에 반복 횟수를 줄여야하는 문제가 되고, 상위의 문제가 결국 최대 물의 양을 반환하는 것이기 때문에, 반복을 항상 물의 양이 더 커질 수 있는 방향으로 두 Line을 결정한다면 쓸 때 없는 반복을 줄일 수 있다.
• 물의 양은 두 Line중 더 낮은 Line의 길이인 low와 두 Line간의 위치차이 (j-i)에 의해 결정된다.
• 이때 (j-i)를 계속 줄어드는 방향으로 강제하고 low를 update하는 방향을 두 Line중 더 낮은 Line의 Pointer를 옮기는 방식은 Pointer를 update했을 때 더 많은 물의양을 가질 가능성이 더 높아지고, 데이터를 덜 볼 수 있게 된다 (주저리주저리).

1. Height의 처음과 끝에 두개의 Pointer start와 end
2. 물의 양 water는 min(height[start], height[end]) * (end - start)로 계산한다.
3. max_water보다 water가 더 크면 max_water를 water로 갱신한다.
4. height[start]가 height[end]가 더 짧으면 start=start+1한다.
5. height[start]가 height[end]가 더 길거나 같으면 end=end-1한다.
6. start가 end보다 작을동안 2~5를 반복한다.
7. max_water를 return한다.

Complexity

• Time complexity:

  Brute force를 사용한다면 \(O(n^2)\), 최적화된 알고리즘 (aka. Two pointer approach)로 한다면 \(O(n)\)

• Space complexity: \(O(1)\)

My Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_water, water = 0, 0
        start, end = 0, len(height) - 1
        while start != end:
            shorter = min(height[start], height[end])
            water = shorter * (end - start)
            if max_water < water:
                max_water = water

            if height[start] < height[end]:
                start += 1
            else:
                end -= 1
                
        return max_water

이 문제에는 사실 맹점이 있다.

그것은 바로 두 Line의 길이가 같을 때의 지침이 없다는 것이다.

Testcase를 통과하는 방향으로 코드를 완성한다면 Accepted 되긴하지만,

두 Line이 같을 때 start = start+1을 해야할 상황도 있을 수가 있다.