Problem of The Day: Find Peak Element

Problem Statement

Intuition

The problem at hand is to find a peak element in an array. A peak element is an element that is strictly greater than its neighbors. The intuition behind solving this problem is to use a modified binary search, as this will allow us to find the peak element efficiently without needing to check every element in the array.

Approach

The approach used here is a recursive binary search. We define a helper function dfs (depth-first search) that takes in the array and two pointers, l and r, representing the current search range. The middle element of the range is calculated and compared with its neighboring elements to check if it is a peak element.

1. Middle Element Check: If the middle element is greater than both of its neighbors, it is a peak element, and we return its index.
2. Divide and Conquer: If the middle element is not a peak, we recursively search both the left and right halves of the array to find the peak element, and then return the maximum result of these two searches.
3. Base Case: If l exceeds r, it means there are no peak elements in the current range, and we return -1.

This recursive strategy helps reduce the problem size by half in each step, leading to an efficient solution.

Complexity

• Time complexity:

  • The time complexity of this approach is \(O(\log n)\). This is because in each recursive call, we are halving the search space, similar to binary search.

• Space complexity:

  • The space complexity is \(O(\log n)\) due to the recursive function calls stacking up in the call stack for each half of the array.

Code

class Solution:
    def dfs(self, nums, l, r):
        while l <= r:
            m = l + (r - l) // 2
            left_val = nums[m - 1] if m - 1 >= 0 else float('-inf')
            right_val = nums[m + 1] if m + 1 < len(nums) else float('-inf')
            if nums[m] > left_val and nums[m] > right_val:
                return m
            else:
                L = self.dfs(nums, l, m - 1)
                R = self.dfs(nums, m + 1, r)
                return max(L, R)
        return -1

    def findPeakElement(self, nums: List[int]) -> int:
        return self.dfs(nums, 0, len(nums) - 1)

Editorial

Approach 2: Recursive Binary Search

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return self.search(nums, 0, len(nums) - 1)

    def search(self, nums: List[int], l: int, r: int) -> int:
        if l == r:
            return l
        mid = (l + r) // 2
        if nums[mid] > nums[mid + 1]:
            return self.search(nums, l, mid)
        return self.search(nums, mid + 1, r)

• time: O(log n)
• space: O(log n)

Approach 3: Iterative Binary Search

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

• time: O(log n)
• space: O(1)