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

Pingback: Median of Two Sorted Arrays | Leetcode Problem #4 - CodeKyro

Pingback: Insertion Sort - A Stable Sorting Algorithm - CodeKyro