Last Updated: 10 Feb, 2021
Least Greater Element
Moderate
Asked in companies
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 ].
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
Approaches
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:
- 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].
- If ARR [j] is greater than ARR [i], then
- Update ARR [i] to leastGreaterElement.
The idea is to traverse the array from right to left and insert each of the array elements one by one into a Binary Search Tree. The Least Greater Element for any array element will be the inorder successor of that node in the Binary Search Tree and -1 if no inorder successor exists.
The inorder successor of a node in a Binary tree is that node which will be visited immediately after the given node in inorder traversal of the tree. The inorder traversal of a binary search tree is the traversal method in which for any node its left subtree is visited first, then the node itself and then the right subtree.
This can be observed by the fact that the Inorder Traversal of a BST is sorted in non-decreasing order, therefore the smallest element having a value greater than a particular array element will be the node value placed exactly right to that element in the inorder traversal of the Binary Search Tree, i.e. its Inorder Successor. To find the Inorder Successor, we can modify the Insert Function of the Binary Search Tree to calculate the successor while inserting the node into BST.
Working of the BST Insert function
- It takes the tree’s root, the node value val, and a global successor node initialized to 'NULL' as its parameters.
- If the tree’s root is 'NULL' create a new node, mark it as the root of the Binary Search Tree and return the root.
- If root -> data is greater than val, then we will update root as the successor node and set root -> left as the value returned by the left subtree’s recursive call. Setting root as the inorder successor works because it can be seen that in Inorder traversal we first visit the left subtree, then the tree's root and then it's right subtree. Here we are moving to the left subtree of the root node, therefore it is guaranteed that we will be visiting the root node after traversing the left subtree. Hence, root can be it's inorder successor. The successor node can point to different nodes while inserting val into the BST. The final node to which the successor node points will be the actual inorder successor of the newly inserted node.
- Otherwise, set root -> right as the value returned by the recursive call for the right subtree.
Now we will traverse the Binary Search Tree from right to left and for every element Initialize its successor node with -1 and insert the current element into the BST. After inserting the value, we will assign the Least Greater Element as the node value of the successor node.
Similar problems