Replace every element of an array with the least greater element on its right

Write an efficient algorithm to replace every element of a given array with the least greater element on its right or with -1 if there are no greater element.


 

For example,


Input:  { 10, 100, 93, 32, 35, 65, 80, 90, 94, 6 }

Output: { 32, -1, 94, 35, 65, 80, 90, 94, -1, -1 }

 

Simple solution would to check if every array element has successor to its right or not by using nested loops. The outer loop picks elements from left to right of the array and the inner loop searches for the smallest element greater than the picked element and replace the picked element with it. The time complexity of this solution would be O(n2).

 

Download   Run Code

Output:

32 -1 94 35 65 80 90 94 -1 -1

 
Another solution is to use BST. The idea is to traverse the array from right to left and insert each element into the BST. Each element in the array is replaced by its inorder successor in BST or by -1 if its inorder successor doesn’t exist.

C

Download   Run Code

Output:

32 -1 94 35 65 80 90 94 -1 -1

C++

Download   Run Code

Output:

32 -1 94 35 65 80 90 94 -1 -1

The time complexity of above solution remains O(n2), but it can be reduced to O(nlogn) using height balanced trees. The worst case happens when the input array is sorted in either ascending or descending order.

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of