Find Peak Element

Posted: 8 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given an array of ‘n’ integers arr. Find the Peak element of the array. The peak element of an array is defined as that element which is greater than both of its neighbours. I.e if arr[i] is the peak element, arr[i-1]<arr[i] and arr[i+1]<arr[i].

It is guaranteed that there exists only one peak element in the array.
Note:
1.Do not print anything, just return the value of peak element of the array.
2.The first element can be the peak element if and only if the array is non increasing.
3.The last element can be the peak element if and only if the array is non decreasing.
4.Consider 0 based Indexing.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘n’ denoting the number of elements in the given sequence. 


The second line of each test case contains ‘n’ space-separated integers denoting the elements in the sequence.
Output Format
For each test case, return a single integer denoting the peak element of the array
Constraints:
1 <= T <= 50
1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of elements in the sequence and arr[i] denotes the ‘i-th’ element of the sequence.

Time limit: 1 second
Sample Input 1:
2
5
1 2 3 2 1
5
7 8 9 6 4
Sample Output 1:
  3
  9
Explanation of sample input 1 :
Test Case 1:
In the given array we can see that the peak element is 3 because the element to its left and right is 2 which is less than 3. If we take any other element lets say the element at index 1 which is 2 (0-based indexing) we see the element to its left is 1 which is less but the element to its right is 3 which is not less therefore 2 can not be a peak element of the array.

Test Case 2:
In the given array we can see that the peak element is 9 because the element to its left is 8 which is less than 9. Also, the element to its right is 6 which is less than 9.If we take any other element lets say the element at index 1 which is 8 (0-based indexing) we see the element to its left is 7 which is less but the element to its right is 9 which is not less therefore 8 can not be a peak element of the array.
Sample Input 2:
2
5
2 3 4 1 -4
6
1 2 3 4 5 6
Sample Output 2:
4
6
Approach 1
  • 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 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.
Try Problem