[LC] 11. Container With Most Water

[seungriyou]

https://leetcode.com/problems/container-with-most-water/

Approach

two pointer로 접근한다. 단, 양끝에서 안쪽으로 이동하는 방식으로!

• 두 pointer 중, height가 작은 쪽의 pointer를 안쪽으로 이동한다.

• 두 pointer의 height가 동일하다면, 하나의 pointer만을 이동한다고 해서 water의 새로운 최댓값을 찾을 수 없기 때문에 두 pointer를 모두 이동한다.

  

while left < right:
    # water 업데이트
    water = max(water, (right - left) * min(height[left], height[right]))

    # height가 작은 쪽의 pointer를 안쪽으로 움직이기
    if height[left] < height[right]:
        left += 1
    elif height[left] > height[right]:
        right -= 1
    # 양쪽의 height가 동일하다면, 하나의 pointer만 이동한다고 해서 현재의 water보다 큰 값을 찾을 수 없으므로
    # 두 pointer 모두 이동하기
    else:
        left += 1
        right -= 1

사실 두 pointer의 height가 동일한 경우를 따로 확인하지 않아도 된다! 어차피 똑같다...

while left < right:
    # water 업데이트
    water = max(water, (right - left) * min(height[left], height[right]))

    # height가 작은 쪽의 pointer를 안쪽으로 움직이기
    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

Complexity

• Time: O(n)
• Space: O(1)