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

In this post we solve the problem to replace every element with the greatest element on right side in an array.

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

Given 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 .

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

Let the input array bearr[] = { 5, 8, 12, 10, 4, 6 }Output array ={ 12, 12, 10, 6, 6, -1}arr[0] = 12as it is the greatest on the right.arr[3] = 6as it is the greatest on the right of 10 .

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

### Method 1: Simple

In this method we make use of two loops. The outer loop traverses the array one by one and the inner loop 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:**

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

#### How to replace every element with the greatest element on right side in an array problem Solution working code in C++:

#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 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:**

- Start from the rightmost element.
- Move towards left one by one.
- Replace every element with the maximum element.

#### Working code in C++on How to replace every element with the greatest element on right side in an array problem :

#include <bits/stdc++.h> using namespace std; /*Function to print the elements of an 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) { /* Initialize the next greatest element */ int max_from_right = arr[n-1]; /* The next greatest element for the rightmost element is always -1 */ arr[n-1] = -1; /*Replace all other elements with the next greatest*/ for(int i = n-2; i >= 0; i--) { /* Store the current element (needed later for updating the next greatest element)*/ int temp = arr[i]; /* Replace current element with the next greatest*/ arr[i] = max_from_right; /* Update the greatest element, if needed*/ if(max_from_right < temp) max_from_right = temp; } } /* 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); cout<<"\nThe modified array is: "; printArray (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)**

**Space Complexity:O(1)**