Find Indices For Local Minimas and Maximas

Easy
0/40
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
OlaUberZomentum

Problem statement

Given an array “arr” of “N” integers. Your task is to find and return all the indices of local minima and local maxima in the given array. You need to return the indices in a 2-D list where the first(0th) row denotes the indices of local minima and the second row denotes the indices of local maxima. In case if there is no local minima or maxima return -1 as the only row element.

We say that an array element arr[i] is a local minimum if it is less than to its neighbours, and local maximum if it is greater than to its neighbours.

Note: 
For corner elements, we need to consider only one neighbour for comparison.
For Example: 
For the given array :  10 5 20 30 40 35 50

picture

The red circle at index 1,5 are local minima because elements at index 1, and 5 both are smaller to its neighbours.

The green circle at index 0,4,6 are local maxima, because element at index 4 is greater than its neighbours, and element at 0, and 4 are corner elements and also greater than its one neighbour.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed.

Then the test case follows.

The first line of each test case contains integer N denoting the size of the array.

The second line of each test case contains 'N' single space-separated integers representing the array elements.
Output Format: 
For each test case
In the first line, print all the space-separated indices of local minima in the given array

In the second line, print all the space-separated indices of local maxima in the given array.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
2 <= N <= 10^5  
-10^9 <= arr[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
3
-10 0 -10
2
4 -2
Sample Output 1 :
0 2
1 
1
0
Explanation for sample 1:
For the first test case, the element at index 1 is greater than its neighbours (element at index 0, and 2), thus it is the local maxima, and the elements at index 0 and index 2 are corner elements and also smaller than their one neighbours, thus they are the local minima.

For the second test case, the element at index 0 is the corner element and also greater than its one neighbour, thus it is local maxima, and the element at index 1 is also the corner element and also smaller than its one neighbour thus it is local minima.
Sample Input 2 :
2
7
10 5 20 30 40 35 50
3
1 2 2
Sample Output 2 :
1 5
0 4 6
0
-1
Hint

Think of iterating the array and checking the neighbours.

Approaches (1)
Brute Force

The idea is to iterate through the given array and at each index i, we check its neighbors to check if it's local minima or maxima.

 

Steps:

 

  • We create two lists namely minima and maxima, to store all the indices of local minima and local maxima respectively.
  • First, we check for the local maxima and minima conditions for the first element.
  • Then we iterate through the given array from index 1 to N - 2, and at any index i, we do the following:
    • If arr[i – 1] > arr[i] < arr[i + 1] then add index i to minima.
    • If arr[i – 1] < arr[i] > arr[i + 1] then add index i to maxima.
  • Then, we check for the local maxima and minima conditions for the last element.
  • At last, we add both lists minima and maxima to answer and return the answer.
Time Complexity

O(N), where N is the length of the given array.

 

In the worst case, we will traverse the array once that takes O(N). Hence the overall complexity will be O(N). 

Space Complexity

O(N), where N is the length of the array.

 

In the worst case, we will be storing all the indices of the array.

Code Solution
(100% EXP penalty)
Find Indices For Local Minimas and Maximas
Full screen
Console