### Replace every element with the greatest element on right side in an array

We are given with an array of integers,we need to replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element,we have to  replace it with -1.
Greatest element on the right side means  the element of the array which is on the right side of the given element and is the greatest number .

### 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.
#include <bits/stdc++.h> using namespace std; /*Function to print the elements of the array*/ void printArray(int arr[] ,int n) { for(int i = 0;i < n;i++) cout<<arr[i]<<" "; } /*Function to print the modified array after replacing every element with the greatest on it's right */ void NextGreatest(int arr[], int n) { int max; /*Outer loop for picking elements*/ for(int i = 0;i < n;i++) { max = 0 ; /*Inner loop for finding greatest on right*/ for(int j = i+1;j < n;j++) { if(arr[j] > max) max = arr[j]; } int temp = arr[i]; arr[i] = max; } arr[n-1] = -1;//Changing last element to -1 cout<<"\nThe modified array is: "; printArray(arr , n); } /* Driver program to test above function */ int main() { int arr[] = {5, 8, 12, 10, 4, 6}; int size = sizeof(arr)/sizeof(arr[0]); cout<<"Given array :"; printArray(arr,size); NextGreatest (arr, size); return 0; }

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`

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

#### More Articles of Rahul Titoria:

Name Views Likes
Replace every element with the greatest element on right side in an array 1228 0