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]
Scroll to Top