Last Updated: 13 Dec, 2021

Peak Value

Moderate

Asked in companies

Solve now

Problem statement

You are given an array ‘arr’, your task is to find an element, such that it is strictly larger than its left and right neighbour and return its index in the array.

Note:

Assume that the first and the last element of the array is -∞.

For Example:

You are given ‘arr’ = [4, 6, 3, 2], Here element 6 is greater than 4 as well as 3, the index of 6 is 1. Hence the answer is 1.

Input Format:

The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the length of the ‘arr’ array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array ‘arr’.

Output Format:

For each test case, return a single integer representing the index of the peak value of the element. 

It is guaranteed that a solution will always be possible under the given constraints. 

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^6
2 <= |arr[i]| <= 10^8
arr[i] != arr[i + 1] for all valid i

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will iterate through the whole array, and check for a possible solution, when the first index of the solution is found we will return it.

Algorithm:

If length of arr is equal to 1 return 0
Iterate i from 0 to the last index of ‘arr’ - 1
- If i is equal to 0 and arr[i] is greater than arr[i + 1]
  - Return i
- If arr[i] is greater than arr[i - 1] and arr[i] is greater than arr[i + 1]
  - Return i
Return length of arr - 1

Solve now

02 Approach

In this approach, we will use binary search on the array. First, it doesn’t seem that binary search will work in an unsorted array but it does.

What we are essentially doing is going in the direction of the rising slope(by choosing the element which is greater than current). How does that guarantee the result? Think about it, there are 2 possibilities.

The Rising slope has to keep rising till the end of the array
The rising slope will encounter a lesser element and go down. In both scenarios, we will have an answer.

In 1. the answer is the end element because we take the boundary as -INFINITY

In 2. the answer is the largest element before the slope falls.

Algorithm:

Set left as 0.
Set right as the size of the ‘arr’ array - 1.
While left is less than right
- Set mid as left + (right - left) / 2
- Set nextNum as mid + 1
- If arr[mid] is less than arr[nextNum]
  - Set left as nextNum
- Otherwise, set right as mid
Finally return left

Solve now