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

Given an array, this function will replace every element in the array with the greatest element in the right side in an array. Since we have no element next to the last element we have to replace it with -1.

Here greatest element is the element that is greatest of all the elements on the right side of the current element

Lets take an example

INPUT:
arr[] = {3, 9, 6, 8, 5}

OUTPUT:
Output array is {9, 8, 8, 5, -1}

In the above example, the greatest element on the right side of 3 is 9, on the right side of 9 is 8 and so on.

Time Complexity: O()

Algorithm

1. simply run two loops

2. In the outer loop, pick an each element in the array ie, i = 0 to n, where n is the size

3. In the inner loop, search for the greatest element after the picked element. ie, j= i+1 to n

4. Replace the picked element with the greatest element and make the last element to -1.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int greatestElement(int arr[], int n)
{
	int greatest;
	for (int i = 0; i < n; ++i)
	{
		greatest = 0;
		for (int j = i +1 ; j < n; ++j)
		{
			if (arr[j]> greatest) //if element is greater than greatest
			{
				greatest = arr[j]; //replace greatest
			}	
		}
		arr[i] = greatest; //replace the element with the greatest of all elements on right
	}
	arr[n-1] = -1;
	cout<<"Output array is "<<"{"; 
	for (int i = 0; i < n; ++i)
	{
		cout<<arr[i]<<" ";
	}
	cout<<"}";
}


int main()
{
	
	int arr[]= {3, 9, 6, 8, 5};  //creating an array
    int n = sizeof(arr)/sizeof(arr[0]); //size of the array
    greatestElement(arr, n);
    return 0;
}
Try It

Time Complexity: O(n)

Algorithm

1. Traverse the array from end to start

2. Initialize greatest element to the last element.

3. While moving left one by one, update the greatest element and replace every element with the greatest element.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int greatestElement(int arr[], int n)
{
	int greatest = arr[n-1]; //initialize greatest to last element
	for (int i = n-2; i >= 0; --i)
	{
		int temp = arr[i]; //check eack element i greater than greatest or not
		arr[i] = greatest; //replace element with greatest.
		if (temp>greatest)
		{
			greatest = temp; //update greatest 
		}
	}
	arr[n-1] = -1;
	cout<<"Output array is "<<"{"; 
	for (int i = 0; i < n; ++i)
	{
		cout<<arr[i]<<" ";
	}
	cout<<"}";
}


int main()
{
	
	int arr[]= {3, 9, 6, 8, 5};  //creating an array
    int n = sizeof(arr)/sizeof(arr[0]); //size of the array
    greatestElement(arr, n);
    return 0;
}
Try It


Next > < Prev
Scroll to Top