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

Leave a Comment / By /
  • 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]

You may also like:

Prime number generator in java using Sieve of Eratosthenes algorithm

Find a missing number in an array of distinct integers in java (example)

Majority element in integer array (Boyer Moore’s voting algorithm) in java

Find leader elements/numbers in integer array (java/example/iterative algorithm)

Find intersection/common elements of two sorted integer arrays in java (example)

Find union of two sorted integer or number arrays in java (example)

Reverse an integer array in java using iterative & recursive algorithm