Leetcode 162: Find Peak Element

The original question can be found here.

It’s asking us to find an element that is grater than both left and right neighbors. Since it’s asking for a O(logn) solution, let’s directly jump to the binary search solution.

There’re 4 cases we we compare an element with its neighbors:

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid - 1] < nums[mid] < nums[mid + 1]:
                start = mid
            elif nums[mid - 1] > nums[mid] > nums[mid + 1]:
                end = mid
            elif nums[mid - 1] > nums[mid] and nums[mid + 1] > nums[mid]:
                start = mid
            else:
                return mid
        
        return start if nums[start] > nums[end] else end

Time Complexity: O(logn). Space Complexity: O(1).