Replace the element with the greatest element on the right side of an array in C++

By Manisha Rathore

In this tutorial, we will learn to replace the element with the greatest element on the right side in C++. Also, we have given an array and we have to replace the element with the greatest element.

NOTE: Moreover, we will replace the last element with -1. Because there is nothing left after that element.

For Example: 

• Given array: { 17, 4, 18, 3, 1, 5, -2 }
• Replace the element with which is the largest element in the right.
• Output will be:  { 18, 18, 5, 5, 5, -2, -1  }

Approach:

Simple Method:

• Firstly, iterate through two for loops.
• The outer loop will go through elements one by one starting from left to right.
• The inner loop will find the greatest element among them.
• Finally, the outer loop will replace the current element with the greatest element.
• The time complexity: O(n^2)

Efficient method:

• Firstly, iterate through only one for loop. This will definitely reduce the time complexity of our code.
• We will start from the rightmost element and will move towards the right.
• Every time we will keep a record of the greatest element.
• Simultaneously, we will replace the element with the greatest element.
• Time complexity: O(n)

You may also like:
Find and replace in a sentence or string in C++

Replace the element with the greatest element on the right side of an array in C++

Implementation:

// C++ Program to replace
#include<iostream>
#include <bits/stdc++.h> 
using namespace std; 

// Function to replace element with greatest
void replacegreatest(int arr[], int ab) 
{ 
  
  // Initialize the next greatest element 
  int maxin_righ = arr[ab-1]; 
  
  // The greatest element for rightmost 
  arr[ab-1] = -1; 
  
  // Replace all other elements 
  for(int i = ab-2; i >= 0; i--) 
  { 
    // store element in a variable
    int x = arr[i]; 
  
    // Replace element with greatest 
    arr[i] = maxin_righ; 
  
    // Update the greatest element if satisfied
    if(maxin_righ < x) 
    maxin_righ = x; 
  } 
} 

// printing array
void printm(int arr[], int ab) 
{ 
   
  for (int i = 0; i < ab; i++) 
    cout << arr[i] << " "; 
  cout << endl; 
} 

int main() 
{ 
  int arr[] = {17, 4, 18, 3, 1, 5, -2}; 
  int ab = sizeof(arr)/sizeof(arr[0]); 
  replacegreatest (arr, ab); 
  
  printm (arr, ab); 
  return 0; 
} 

Output Explanation:

INPUT: {17, 4, 18, 3, 1, 5, -2 }
OUTPUT: {18, 18, 5, 5, 5, -2, -1}