Method 1: Simple

In this method we will make use of two loops. The outer loop traverses the array one by one and the inner loop will finds the greatest element in the array present after the picked element. The outer loop finally replaces the traversed element by the greatest element found by the inner loop.

Algorithm:

1. Pick elements one by one using the outer loop.
2. Search for greatest element in an array after the picked element using the inner loop.
3. Swap both the elements using the outer loop.

 Output:

Given array :5 8 12 10 4 6

The modified array is: 12 12 10 6 6 -1

Time Complexity:O(N*N)
Space Complexity:O(1)

Method 2: Tricky

In this method we will replace all elements using one traversal of the array. The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element.

Algorithm:

1. Start from the rightmost element.
2. Move towards left one by one.
3. Replace every element with the maximum element.

// C++ program to replace every element with the 
// least greater element on its right 
#include <iostream> 

using namespace std; 

  
// A binary Tree node 

struct Node 
{ 

    int data; 

    Node *left, *right; 
}; 

  
// A utility function to create a new BST node 

Node* newNode(int item) 
{ 

    Node* temp = new Node; 

    temp->data = item; 

    temp->left = temp->right = NULL; 

  

    return temp; 
} 

  
/* A utility function to insert a new node with 

   given data in BST and find its successor */

void insert(Node*& node, int data, Node*& succ) 
{ 

    /* If the tree is empty, return a new node */

    if (node == NULL) 

        node = newNode(data); 

  

    // If key is smaller than root's key, go to left 

    // subtree and set successor as current node 

    if (data < node->data) 

    { 

        succ = node; 

        insert(node->left, data, succ); 

    } 

  

    // go to right subtree 

    else if (data > node->data) 

        insert(node->right, data, succ); 
} 

  
// Function to replace every element with the 
// least greater element on its right 

void replace(int arr[], int n) 
{ 

    Node* root = NULL; 

  

    // start from right to left 

    for (int i = n - 1; i >= 0; i--) 

    { 

        Node* succ = NULL; 

  

        // insert current element into BST and 

        // find its inorder successor 

        insert(root, arr[i], succ); 

  

        // replace element by its inorder 

        // successor in BST 

        if (succ) 

            arr[i] = succ->data; 

        else // No inorder successor 

            arr[i] = -1; 

    } 
} 

  
// Driver Program to test above functions 

int main() 
{ 

    int arr[] = { 5 8 12 10 4 6 }; 
    

int n = sizeof(arr)/ sizeof(arr[0]); 

  

    replace(arr, n); 

  

    for (int i = 0; i < n; i++) 

        cout << arr[i] << " "; 

  

    return 0;
}

Output :

Given array :5 8 12 10 4 6 

The modified array is: 12 12 10 6 6 -1