Replace every element in integer array by greatest number on its right (java/ example)

• Given an array of integers in java.
• Replace every element of array with greatest number on its right.
• The right most element will always replaced by -1.

1. Examples: replace every elements by maximum number on its right (java)

1.1 Example #1:

• Given an integer array { 4, 10, 7, 5 }
• Find out the greatest element, for each number in an integer array.
  • e.g We want to replace 4 by greatest element on its right.
  • 10 is the maximum element on the right side of 4.
    • So, 4 will be replaced by 10.
  • Similarly, if want to replace 1o by greatest element on right.
  • 7 is the greatest element on the right.
    • So, 10 will be replaced by 7.
• Output of current example is : {10, 7, 5, -1}

1.2 Example #2:

• Given an integer array { 10, 12, 20, 15, 17, 8}
• Find out the greatest element, for each element in an integer array.
  • e.g We want to replace 10 by greatest element on its right.
  • 20 is the maximum element on the right side of 10.
    • So, 10 will be replaced by 20.
  • Similarly, if want to replace 20 by greatest element on right.
  • 17 is the greatest element on the right.
    • So, 20 will be replaced by 17.
• Output of current example is : {20, 20, 17, 17, 8, -1}

2. Algorithm – replace every in array elements by greatest number in java

1. Traverse the array from right to left.
2. Replace last element by -1.
3. Initialize maxElement with last element of array.
4. Traverse input array from right to left
   • Take the backup of current element.
   • Replace current element by maxElement
   • If current element greater than maxElement
     • update the maxElement by current element
5. end of array traversal
6. All elements in an array is replaced by max element on its right.

Time complexity of algorithm is O (n).

3. Program – replace every element in array by maximum number in java

package org.learn.arrays;

import java.util.Arrays;

public class ReplaceByGreatest {
	
	public static void main(String[] args) {
		
		int []arr = {4, 10, 7, 5};
		System.out.printf("1. Input array : %s ", Arrays.toString(arr));
		replaceElements(arr);
		
		arr = new int []{10, 12, 20, 15, 17, 8};
		System.out.printf("\n\n2. Input array : %s ", Arrays.toString(arr));
		replaceElements(arr);
	}
	
	private static void replaceElements(int []arr) {
		int lastIndex = arr.length - 1;
		int maxElement = arr[lastIndex];
		arr[lastIndex--] = -1;

		while (lastIndex >= 0) {
			int current = arr[lastIndex];
			arr[lastIndex] = maxElement;
			if (current > maxElement) {
				maxElement = current;
			}
			lastIndex--;
		}		
		System.out.printf("\nElements replaced by greatest: %s",Arrays.toString(arr));
	}
}

4. Output – replace every element in array by maximum number in java

1. Input array : [4, 10, 7, 5] 
Elements replaced by greatest: [10, 7, 5, -1]

2. Input array : [10, 12, 20, 15, 17, 8] 
Elements replaced by greatest: [20, 20, 17, 17, 8, -1]