Least Greater Element

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
11 upvotes
Asked in companies
InnovaccerOla

Problem statement

You are given an array 'ARR' of Integers. Your task is to replace each element of the array with the smallest element, which is strictly greater than that element and is present on the right side of that element in the array i.e. for each valid index ‘i’ replace ARR[i] with the smallest ARR[j] such that ARR[j]>ARR[i] and j>i.

In case there exists no such element satisfying the above conditions for a particular array element, replace it with -1.

For example :

Consider the array ARR = [ 1, 4, 2, 6 ] having 4 elements.
The array containing the Least Greater Elements for the above array will be [ 2, 6, 6, -1 ].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains an integer 'N', denoting the number of elements in the array 'ARR'.

The second line of each test case contains 'N' space-separated integers denoting the array elements.
Output Format : 
The only line of output of each test case should contain 'N' space-separated integers denoting the Least Greater element for each of the 'N' array elements.
Print the output of each test case in a new line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^4
0 <= ARR[i]  <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the elements in the array 'ARR', and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.

Time Limit: 1 sec
Sample Input 1 :
2
4
5 6 7 2
3 
4 3 6
Sample Output 1 :
6 7 -1 -1 
6 6 -1
Explanation for Sample Input 1 :
For the first test case : 
1) For ARR [0] = 5, the least greater element is 6.
2) For ARR [1] = 6, the least greater element is 7.
3) For ARR [2] = 7, no least greater element exists. Hence, we will consider -1 here.
4) For ARR [3] = 2, no least greater element exists. Hence, we will consider -1 here.
Therefore, the output array is [ 6, 7, -1, -1 ] in this case.

For the second test case : 
1) For ARR [0] = 4, the least greater element is 6.
2) For ARR [1] = 3, the least greater element is 6.
3) For ARR [2] = 6, no least greater element exists. Hence, we will consider -1 here.
Therefore, the output array is [ 6, 6, -1 ] in this case.
Sample Input 2 :
2
3
6 2 6
4
5 6 1 4
Sample Output 2 :
-1 6 -1
6 -1 4 -1
Hint

Try to find out the Least Greater Element for each of the array elements by iterating to the right of that element and comparing it with each element.

Approaches (2)
Brute Force Approach

The idea is to find the Least Greater Element for each array element one by one. To find the Least Greater Element for an array element, we will start moving to the right of that element and set the Least Greater Element as the smallest element having a value greater than that element. If we reach the end of the array without finding any element having a greater value, then we will set the least greater element as -1 for that element.

 

Steps:

 

  1. Iterate from i = 0 to N - 1
    • Set leastGreaterElement as -1.
    • Iterate from j = i + 1 to N -1 
      • If ARR [j] is greater than ARR [i], then
        • If leastGreaterElement is equal to -1, then update leastGreaterElement to ARR [j]. 
        • Otherwise, update leastGreaterElement to the smaller value among leastGreaterElement and ARR [j].
    • Update ARR [i] to leastGreaterElement.

 

Time Complexity

O(N^2), where N is the number of elements in the array.

 

In the worst case, It takes O(N) time to find the Least Greater element for each of the N array elements. Hence, the overall Time Complexity is O(N^2).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Least Greater Element
Full screen
Console