Problem

Submissions

Hints & solutions

Discuss

Peak Value

Moderate

0/80

Contributed by

19 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
4
4 6 3 2
6
1 2 3 4 5 3

Sample Output 1:

1
4

Explanation:

For the first test case, ‘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.

For the second test case, ‘arr’ = [1, 2, 3, 4, 5, 3], Here element 5 is greater than 4 as well as 3, the index of 5 is 4. Hence the answer is 4.

Sample Input 2:

2
4
1 2 5 3
5
3 8 9 30 10

Sample Output 2:

 2
 3

Hint 1

Hint 2

Try to check the condition of the problem statement for each index of the array by iterating it.

Approaches (2)

Approach 1

Approach 2

Iterative 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

Time Complexity

O(N), Where N is the size of the array.

We are iterating over the whole array once. Hence the final time complexity is O(N).

Space Complexity

O(1),

No extra space is used in this algorithm

(100% EXP penalty)

Peak Value

Console