162.Find_Peak_Element(Medium).md

162. Find Peak Element (Medium)

Date and Time: Jul 19, 2024, 16:10 (EST)

Link: https://leetcode.com/problems/find-peak-element/

Question:

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]

Output: 2

Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]

Output: 5

Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Edge case:

Input: nums = [1]

Output: 0

Constraints:

• 1 <= nums.length <= 1000

• -2^{31} <= nums[i] <= 2^{31} - 1

• nums[i] != nums[i + 1] for all valid i.

KeyPoints:

We start from the mid point because it requires $O(log\ n)$ runtime, it is natural to use binary search. To find peak element, we can only look at 3 elements in a row, e.g. [1,3,1], 3 is the peak element. So we only compare nums[m] and its neighbors nums[m-1], nums[m+1], if there exists a greater element in neighbors, we start searching from there, otherwise, nums[m] is the peak element and we return it.

We need to check bound first to prevent the edge case, when m = 0 or m = len(nums)-1 we can't find its left or right neighbor.

My Solution:

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # Run Binary Search to check, if nums[i] > nums[i-1] and nums[i] > nums[i+1]
        # if nums[i] < nums[i+1], update l = i+1, hope the new value can be the peak element
        # if nums[i] < nums[i-1], update r = i-1

        # TC: O(log n), SC: O(1)
        l, r = 0, len(nums)-1
        while l <= r:
            i = (l+r) // 2
            if i > 0 and nums[i] < nums[i-1]:
                r = i - 1
            elif i < len(nums)-1 and nums[i+1] > nums[i]:
                l = i + 1
            else:
                return i

Time Complexity: $O(log\ n)$
Space Complexity: $O(1)$