Replace each element with next greatest

© Parineeth M R

Question 18. Replace each element in an array with the next greatest


Consider the array A = {0, 2, 8, 1, 3, 5, 4}.

The greatest number after 0 in A is maximum of {2, 8, 1, 3, 5, 4} = 8. So 0 is replaced by 8.

The greatest number after 8 in A is maximum of {1, 3, 5, 4} = 5. So 8 is replaced with 5.

4 is the last number in A. There are no more elements to its right. So 4 is replaced by an invalid number or the smallest possible number.

So the resulting array is = {8, 8, 5, 5, 5, 4, INVALID_NUMBER}.

The brute force approach will try to compute the next greatest of an element by scanning all the elements to its right. This will have a time complexity of O(n2).

However we can achieve the same in O(n) by traversing from the end of the array to the beginning and maintaining the maximum element seen so far. The code is given below

C/C++


/*
a: array in which each element should be replaced with next greatest
n: number of elements in the array. n >= 1
*/
void replace_with_next_greatest(int a[], int n) {
	int i, next_greatest, temp;

	next_greatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array from backwards*/
	for (i = n-2; i >= 0; --i) {
		temp = a[i];

		a[i] = next_greatest;

		if (temp > next_greatest)
			next_greatest = temp;
	}
}



Java


/*
a: non-empty array in which each element should be replaced with next greatest
*/
public static void replaceWithNextGreatest(int[] a) {
	int n = a.length;
	int nextGreatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array backwards*/
	for (int i = n-2; i >= 0; --i) {
		int temp = a[i];

		a[i] = nextGreatest;

		if (temp > nextGreatest)
			nextGreatest = temp;
	}
}



Python


#a: non-empty list in which each element should be replaced with next greatest
def replace_with_next_greatest(a) :
	n = len(a)

	next_greatest = a[n-1]
	a[n-1] = INVALID_NUMBER  

	#Process the list from the back
	for i in range(n-2, -1, -1) :
		temp = a[i]

		a[i] = next_greatest

		if (temp > next_greatest):
			next_greatest = temp