Find Peak Element

Problem Description

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

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

Example 2

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

Constraints

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

Solution Code

Python

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) >> 1

            if nums[mid - 1] <= nums[mid] >= nums[mid + 1]:
                return mid
            elif nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid

        return left

Java

class Solution {
    public int findPeakElement(int[] nums) {
    int n=nums.length;
    if(n==1)return 0;
    if(nums[0]>nums[1])return 0;
    if(nums[n-1]>nums[n-2])return n-1;
    int low=1,high=n-2;
    while(low<=high){
        int mid=(low+high)/2;
        if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])return mid;
        else if(nums[mid]>nums[mid-1])low=mid+1;
        else high=mid-1;
    }
    return -1;    
    }
}

C++

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            } else
                high = mid;
        }
        return low;
    }
};

Javascript

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n == 1)
            return 0;
        else if(nums[0] > nums[1])
            return 0;
        else if(nums[n-1] > nums[n-2])
            return n-1;
        int low = 1, high = n-2;
        while(low <= high) {
            int mid = low + (high - low)/2;
            if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1])
                return mid;
            else if(nums[mid] < nums[mid-1])
                high = mid-1;
            else
                low = mid+1;
        }
        return -1;
    }
}