Find Peak Element

Easy
0/40
Average time to solve is 15m
219 upvotes
Asked in companies
GrabDunzoHike

Problem statement

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.


Detailed explanation ( Input/output format, Notes, Images )
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.


Sample Input 1:
5
1 8 1 5 3


Expected Answer:
1


Output on Console:
True


Explanation of sample input 1 :
There are two possible answers. Both 8 and 5 are peak elements, so the correct answers are their positions, 1 and 3. Any of these 2 numbers will print 'True'.


Sample Input 2:
3
1 2 1


Expected Answer:
1


Output on Console:
True


Expected time complexity:
The expected time complexity is O(log 'n').


Constraints:
1 <= 'n' <= 10^5
1 <= 'arr[i]' <= 10^5
'arr[i]' != 'arr[i + 1]' for all 'i' in range 0 <= 'i' < 'n' - 1


Hint

Check for all elements if they are peak or not.

Approaches (2)
Brute force approach
  • 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.
Time Complexity

O(‘n’), where ‘n’ is the number of elements in the sequence.

We need to traverse the array once to find the peak element.

Hence the time complexity is O(‘N’).

Space Complexity

O(1)

We are using constant space.

Hence the space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Find Peak Element
Full screen
Console