Peak element

Problem Statement - link #

An element is called a peak element if its value is not smaller than the value of its adjacent elements(if they exists). Given an array arr[] of size N, find the index of any one of its peak elements. Note: The generated output will always be 1 if the index that you return is correct. Otherwise output will be 0.

Your Task: You don’t have to read input or print anything. Complete the function peakElement() which takes the array arr[] and its size N as input parameters and return the index of any one of its peak elements.

Can you solve the problem in expected time complexity?

Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Input:
N = 3
arr[] = {1,2,3}
Output: 2
Explanation: index 2 is 3.
It is the peak element as it is 
greater than its neighbour 2.

Example 2:

Input:
N = 2
arr[] = {3,4}
Output: 1
Explanation: 4 (at index 1) is the 
peak element as it is greater than 
its only neighbour element 3.

Constraints #

• 1 <= N <= 10^5
• 1 <= nums[i] <= 10^6

Solutions #

class Solution{
    public:
    int peakElement(int nums[], int n)
    {
       // Your code here
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if( (mid == 0 || nums[mid] > nums[mid - 1]) && (mid == n - 1 || nums[mid] > nums[mid + 1])) 
                return mid;
            else if(nums[mid] > nums[mid - 1]) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};