Problem 6 - Find peak element

Explore our archive for previous posts.

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.

Constraints:

• 1 <= nums.length <= 1000

• -231 <= nums[i] <= 231 - 1

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

Approach

This solution uses a modified version of binary search to find a peak element in an array. The key idea is to compare the middle element with its adjacent element to determine the direction of the peak. If the middle element is less than its right neighbor, it means the peak is on the right side. Otherwise, the peak is on the left side or the middle element itself is the peak. By adjusting the search range based on these comparisons, we can converge to a peak element.

Solution

Solve it here

public class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(log n), where n is the number of elements in the array. This is because it uses a modified version of binary search, which reduces the search space by half in each iteration.

Space Complexity: The space complexity of the solution is O(1) because it uses a constant amount of additional space, regardless of the size of the input array.