Replace every element with the next greatest

Given an array of integers, replace every element with the next greatest element on the right side in the array. Replace last element with 0 as there no element on the right side of it.
eg. if the array is {6, 7, 4, 3, 5, 2}, output {7, 5, 5, 5, 2, 0}

Method 1 (Brute Force):

Use two loops. The outer loop will pick array elements from left to right. The inner loop will find the greatest element present after the picked element. Finally the outer loop will replace the picked element with the greatest element found by inner loop.
Time complexity O(n*n).

Method 2: (Optimized tricky solution)

Replace all elements using one traversal of the array. 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.

void replaceWithNextGreatest(int a[], int size)
{
	int maximum =  a[size-1];
	a[size-1] = 0; // last element is always replace with zero

	// Replace all other elements with the next greatest
	for(int i = size-2; i >= 0; i--)
	{
		int temp = a[i];
		a[i] = maximum;

		// Update the greatest element, if needed
		if(maximum < temp)
			maximum = temp;
	}
}

Time Complexity: O(N)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation