Leetcode 852: Peak Index in a Mountain Array

The original question can be found here.

The question is asking us to return a peak element, which means, an element is greater than both 2 adjacent neighbors.

Brute Force

Scan the array:

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        index, length = 1, len(arr)
        while index < length - 1:
            if arr[index] > arr[index - 1] and arr[index] > arr[index + 1]:
                return index
            index += 1
        return -1

Time complexity: O(n). Space complexity: O(1).

Binary Search

Since the question explictly asking for O(logn) solution, we know we should perform binary search. If middle element is greater than both neighbors, it’s the answer. If it’s greater than left neighbor but smaller than right neighbor, we know we still need to “climb” the mountain, thus focus on right half of the array. If it’s smaller than left neighbor but greater than right neighbor, we know we’re going down hill so need to focus on left half of the array:

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
                return mid
            elif arr[mid] > arr[mid - 1] and arr[mid] < arr[mid + 1]:
                left = mid
            else:
                right = mid
        
        return arr[left] if arr[left] > arr[right] else arr[right]

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