162. Find Peak Element (Array, Binary Search)

링크 - https://leetcode.com/problems/find-peak-element/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

Binary Search를 통해 mid값을 비교하면서 답을 찾아갈 수 있는 문제이다. 여기서는 4가지의 케이스들을 비교해야 한다.

case 1. 왼쪽으로 단조증가하는 경우

5,4,3,2,1 같은 경우를 보자. 이 경우 mid는 3이다. 3의 이웃들을 살펴보면 4와2가 있다. 따라서 미드를 중심으로 왼쪽으로 단조증가 중이다. 따라서 우리는 오른쪽은 신경쓸 필요가 없다. 따라서 우리는 이때 right를 mid로 설정하면 된다.

case2. 오른쪽으로 단조증가하는 경우

1,2,3,4,5같은 경우를 보자. 이 경우 mid는 3이다. 3의 이웃들을 살펴보면 2와 4가 있다. 따라서 미드를 중심으로 오른쪽으로 단조증가 중이다. 따라서 우리는 왼쪽은 신경쓸 필요가 없다. 따라서 우리는 이때 left를 mid+1로 설정하면 된다. 이미 우리는 right를 mid로 설정하기로 했으므로, left를 mid+1이 아닌 mid로 설정하면 2개의 원소만 남았을때 left, right가 변하지 않고 무한루프에 빠질 수 있기 때문이다.

case3. 왼쪽과 오른쪽 사이에 Peak가 있는 경우

2,3,4,5,1같은 경우를 보자. 이 경우 mid는 4이다. 4의 이웃들을 살펴보면 3과 5이다. 따라서 case 2와 같은 오른쪽으로 단조증가하는 경우와 같으므로 left는 mid+1이 된다. 그 다음 경우는 5,1이다. 이 경우 5가 peak가 되므로 이 인덱스를 반환하면 된다.

case4. 왼쪽과 오른쪽 사이에 Valley가 있는 경우

4,3,2,1,5같은 경우를 보자. 이 경우 mid는 2이다. 2의 이웃들을 살펴보면 3과1이다. 즉 case 1과 같은 왼쪽으로 단조증가 하는 경우이다. 따라서 right는 mid가 된다. 이런식으로 해서 4가 peak임을 알아낼 수 있다. 

 

결과적으로 우리는 mid의 값을 중심으로 이웃 원소들을 보면 된다. mid값은 항상 배열의 가장 오른쪽 원소가 될 수 없기 때문에 mid+1의 값과 비교해서 mid가 크면 right를 mid로, 아니라면 left를 mid+1로 설정하면 된다.

Code

# Recursive Binary Search(O(log2(N)) space complexity)
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return self.findPeak(nums, 0, len(nums) - 1)

    def findPeak(self, nums, left, right):
        if left == right:
            return left

        mid = left + (right - left) // 2
        if nums[mid] > nums[mid+1]:
            return self.findPeak(nums, left, mid)
        return self.findPeak(nums, mid+1, right)
        
# Iterative Binary Search(O(1) space complexity)
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid+1]:
                right = mid
            else:
                left = mid + 1

        return left

Complexity

Time Complexity: O(log2(N)) Binary Search덕분에 우리는 탐색 범위를 매번 절반으로 줄이기 때문이다.

Space Complexity: O(log2(N)) 하지만 두번째 방식처럼 recursive가 아닌 iterative하게 하면 O(1)이 된다.