Last Updated: 8 Jan, 2021
Find Peak Element
Easy
Asked in companies
You are given an array 'arr' of length 'n'. Find the index(0-based) of a peak element in the array. If there are multiple peak numbers, return the index of any peak number.
Peak element is defined as that element that is greater than both of its neighbors. If 'arr[i]' is the peak element, 'arr[i - 1]' < 'arr[i]' and 'arr[i + 1]' < 'arr[i]'.
Assume 'arr[-1]' and 'arr[n]' as negative infinity.
Note:
1. There are no 2 adjacent elements having same value (as mentioned in the constraints).
2. Do not print anything, just return the index of the peak element (0 - indexed).
3. 'True'/'False' will be printed depending on whether your answer is correct or not.
Example:
Input: 'arr' = [1, 8, 1, 5, 3]
Output: 3
Explanation: There are two possible answers. Both 8 and 5 are peak elements, so the correct answers are their positions, 1 and 3.
Input format:
The first line contains an integer ‘n’, the number of elements in 'arr'.
The second line contains ‘n’ space-separated integers , the array 'arr'.
Output Format
The output contains True/ False depending whether the found number is peak element or not.
Approaches
- The key idea is to check if each element is a peak or not.
- To do that we first check if one of the first or last element is peak.
- For that, we simply check if the array is sorted in increasing or decreasing order.
- Otherwise, we take a loop from index = 1 and for each element, compare it to its left and right element to see if it is greater than both of them.
- If it is, we have found the peak element and we return it. Otherwise, we check the next element in the array.
Keeping the above example in mind, we can write the following solution:
- We first start with checking if the array is sorted or not. If it is sorted in decreasing order, we return the element at the 0th index as the peak element.
- Otherwise, if sorted in increasing order, we return the last element as the peak element.
- Otherwise, we iterate through the array using a loop and with variable ‘i’ as the iterator and check if the i-th index is peak or not by comparing it with the previous and next element of the array.
- Once we find the peak element we return it.
- The peak element has a unique property that it is greater than its neighbours and this property is unique to the peak element.
- Suppose the sequence is […, 2, 3,…] and we are currently focussing on 2 and 3. There must be at least one peak on the right side of 2. Since 3 has a smaller left neighbour, either it has a smaller right neighbour or not. If it has a smaller right neighbour, then 3 is a peak. Otherwise, the right neighbour has a smaller left neighbour (referring to 3). The sequence cannot be strictly increasing because we have assumed the last element as negative infinity. Therefore there must be at least one peak.
Keeping in mind the above ideas, we can use the following approach:
- We initially define ‘l’ to be the leftmost index i.e. 0 and ‘r’ to be the rightmost index i.e. ‘n’ - 1 where ‘n’ is the size of the array.
- Then we Binary search for the peak. We define ‘middle’ as the middle-point of ‘l’ and ‘r’.
- If the element to the left and right of ‘middle’ is smaller than ‘arr[middle]’, we found our peak, so we return it.
- Otherwise, if the left of ‘middle’ is small and the right is greater, there is at least one peak on the right side. So we update ‘l’ to ‘middle’ + 1.
- Otherwise, there is at least one peak on the right side. So we update ‘r’ to ‘middle’ - 1.
- We do this until we find our peak.
Similar problems