# Find Peak Element

Posted: 8 Jan, 2021

Difficulty: Easy

#### 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 i.e. it will be a peak if its equal to second element.
3.The last element can be the peak element if and only if the array is non decreasing i.e. it will be a peak if it's equal to second last element.
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.

Approach 2

- The key idea is that the sequence is bitonic i.e it is first increasing then decreasing.
- Also, the peak element has a unique property that it is greater than its neighbours and this property is unique to the peak element.
- Think of the array as a mountain and the elements as heights so we can conclude we will have the following structure

- So any element in the left of the peak will have its left element less than itself and right element greater than itself.
- Similarly, any element in the right of the peak will have it left element greater than itself and left element less than itself
- The peak will have both left and right element less than itself.
- We can use the above properties to a binary search through the array to find the peak element.

Keeping in mind the above idea, 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 middlepoint 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 right is greater we are in the left of the peak so we update l to middle+1
- Otherwise, we are on the right of the peak so we update r to l-1.
- We do this until we find our peak.

SIMILAR PROBLEMS

# Two Sum II - Input Array Is Sorted

Posted: 4 Mar, 2022

Difficulty: Moderate

# Ninja And Matrix

Posted: 12 Apr, 2022

Difficulty: Easy

# Ninja In Interview

Posted: 13 Apr, 2022

Difficulty: Easy

# Missing Number

Posted: 17 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate