Leetcode: 162. Find Peak Element

• Pattern: Searching in Array.
• Pattern: Problem's constraints play big role on the solution. The problem requires a logarithmic solution.

• Can we formulate the problem as a classical problem?

There are two ways to search for elements in an array: linear search of Binary Search. The problem statement rules out the first possibility, so the problem becomes finding a way to use Binary Search to solve the problem. Be \(m\) the index of the pivot. If \(nums[m-1]nums[m]\), \(m\) is a valid answer. Otherwise, one neighbor is greater than \(nums[m]\). If \(nums[m-1]>nums[m]\), then \(m-1\) can be an answer iff \(nums[m-2]nums[m-1]\). The same argument can be done for \(nums[m+1]\). The time complexity of the search is \(O(\log n)\) and space is \(O(1)\).

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

• Interview preparation: V