Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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.

Solution

Method 1 - Naive

A simple approach is to do a linear scan to a array and using few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

Method 2 - Binary Search

Here is the approach:

  • Recursively Find the Peak Element: Use a recursive binary search approach to find a peak element.
  • Binary Search: Select the middle element as the potential peak and compare it with its neighbors.
  • Recursion:
    • If the middle element is greater than or equal to its neighbors, return the middle index as the peak.
    • If the middle element is less than its left neighbor, the peak must be to the left.
    • Otherwise, the peak must be to the right.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    // Function to find a peak element using recursion
    public int findPeakElement(int[] nums) {
        return findPeakElementRec(nums, 0, nums.length - 1);
    }

    // Helper function that uses recursion to find the peak element
    private int findPeakElementRec(int[] nums, int low, int high) {
        int mid = low + (high - low) / 2;

        // Check if mid is a peak element
        if ((mid == 0 || nums[mid - 1] <= nums[mid])
            && (mid == nums.length - 1 || nums[mid + 1] <= nums[mid])) {
            return mid;
        }

        // If the left neighbour is greater, then the peak lies in the left half
        if (mid > 0 && nums[mid - 1] > nums[mid]) {
            return findPeakElementRec(nums, low, mid - 1);
        }

        // If the right neighbour is greater, then the peak lies in the right
        // half
        return findPeakElementRec(nums, mid + 1, high);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def find_peak_element(arr):
    return find_peak_recursively(arr, 0, len(arr) - 1, len(arr))
    
def find_peak_recursively(arr, low, high, n):
    mid = low + (high - low) // 2

    # Check if the mid element is greater than or equal to its neighbors
    if (mid == 0 or arr[mid] >= arr[mid - 1]) and (
        mid == n - 1 or arr[mid] >= arr[mid + 1]
    ):
        return arr[mid]

    # If the element on the left side is greater, then there is a peak element on the left side
    elif mid > 0 and arr[mid - 1] > arr[mid]:
        return find_peak_recursively(arr, low, mid - 1, n)

    # If the element on the right side is greater, then there is a peak element on the right side
    else:
        return find_peak_recursively(arr, mid + 1, high, n)

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(log n)