Find Peak Element in Array | Leetcode Problem #162

A peak element is defined as an element that is strictly greater than its neighbor. In this question, you’ll be provided with an array in which you have to find peak element and return its index. In case the array contains multiple peak elements, return the index of any one of the peak elements.

You have to assume that nums[-1] = nums[n] = –inf
For all valid i, nums [i] != nums[i+1] and nums [i] != nums[i-1]

Input: nums = [1, 2, 3, 1]
Output: 2 //since 3 is the peak element and its index is 2

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 //here we have 2 peak elements, 2 and 6. Therefore we have to return index of anyone of the element

Input: nums = [5, 10, 20, 15]
Output: 2

To have a better idea about the problem, have a look at the following cases.

• If the given array is in a strictly decreasing order, then the first element is the peak element. For ex: if nums = [8, 6, 4, 2, 0], then 8 is the peak element.
• If the given array is in a strictly increasing order, then the last element is the peak element. For ex: if nums = [1, 2, 3, 4, 5], then 5 is the peak element.

Naive Solution to Find Peak Element

This is the simplest approach that anyone can think of. In this method, we add INT_MAX at the end and traverse across the array to check if the neighbor elements are strictly smaller than the element. If we find an element then we return its index. Below we have shown the C++ program to find peak element. Time complexity in this method is O(N).

class Solution {
public:
//C++ program to find peak element

    int findPeakElement(vector<int>& nums) {

        int n = nums.size(),i;
        nums.push_back(INT_MIN);

        if(n==1)
            return 0;

        for(i=1;i<n;i++){
            if(nums[i]>nums[i-1] and nums[i]>nums[i+1])//here we are checking the condition for peak element
                return i;
        }

        return 0;
    }
};

Dry Run

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

When i=1, if condition doesn’t get executed as nums[1] <nums[2]
When i = 2, since nums[2] > nums[1] and nums[2] > nums[3], if condition gets executed and hence 2 is returned

Find Peak Element Using Binary Search

This problem can be solved in a much efficient manner. With the help of binary search, we can reduce the time complexity to O(log(N)). In this approach we’ll first find the mid index and check whether it is greater than its neighbour. If yes, then we’ll print the index of element otherwise we’ll check in which side the neighbour element has a greater value. We look for the peak element in the greater element side as the chances of it being a peak element are very high. This way we can find peak element in the given array. Below we have shown the C++ program to find peak element using binary search.

class Solution {
public:
    //here we find peak element using binary search
    int findPeakElement(vector<int>& nums) {

        int n = nums.size();
        int low = 0, high = n-1;

        while(low <= high){

            int mid = (low+high)/2;

            //next we check the condition for peak element
            if((mid == 0 or nums[mid] > nums[mid-1]) and (mid == n-1 or nums[mid] > nums[mid+1]))
                return mid;

            //next conditions are applied to check which part to apply binary search
            if(mid > 0 and nums[mid-1] > nums[mid+1])
                high = mid-1;
            else
                low = mid+1;
        }

        return 0; //if we cannot find peak element we return 0
    }
};

Explanation

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

low = 0, high = 6 =>mid = 3. Since nums[3] is not strictly greater than its neighbour, the first if statement is not executed. Here nums[4] > nums[2], i.e., nums[mid+1] > nums[mid-1], therefore low = mid+1 = 3+1 = 4. In the next iteration we have mid = (4+6)/2 = 5. Since 6 is strictly greater than its neighbour elements, we return its index, i.e., 5.

Hope you find this method interesting and do refer our previous articles like Sieve of Eratosthenes and Window Sliding Technique