Java Program to Replace the Element with its Next Greatest Element, Rightmost Element will be Replaced by 0

Category : Java | Sub Category : Java Programs from Coding Interviews | By Prasad Bonam Last updated: 2021-01-02 14:10:24 Viewed : 601


This is the Java Program to Replace the Element with its Next Greatest Element, Rightmost Element will be Replaced by 0.

Problem Description

Given an array of integers, replace each element of the array with the greatest element present on the right side of the element, in the array. The rightmost element or the last element should be replaced by 0.

Example:
Array = [-1, -3, 3, 2, 8 ,6]

Output: [8, 8, 8, 8, 6, 0].

Problem Solution

Traverse the array from right to left and keep track of the maximum element found. Replace each element with the current maximum element, until the maximum changes. At the point of new maximum, swap the current element with the current maximum and continue. Finally, update the rightmost element to zero.

Program/Source Code

Here is the source code of the Java Program to Replace the Element with its Next Greatest Element, Rightmost Element will be Replaced by 0. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Replace the Element with its Next Greatest Element, 
  3. //Rightmost Element will be Replaced by 0
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7.  
  8. public class ReplaceNextGreatest {
  9.         // Function to replace all the array elements
  10.         // with the next greatest element
  11.         static void nextGreatest(int[] array){
  12.             int max=array[array.length-1];
  13.             int i,temp;
  14.             for(i= array.length-2; i>=0; i--){
  15.                     temp = array[i];
  16.                     array[i] = max;
  17.                     if(temp > max)
  18.                         max= temp;
  19.             }
  20.             array[array.length-1] = 0;
  21.         }
  22.         // Function to read input and display the output
  23.         public static void main(String[] args) {
  24.             BufferedReader br = new BufferedReader
  25.                                 (new InputStreamReader(System.in));
  26.             int size;
  27.             System.out.println("Enter the size of the array");
  28.             try {
  29.                 size = Integer.parseInt(br.readLine());
  30.             } catch (Exception e) {
  31.                 System.out.println("Invalid Input");
  32.                 return;
  33.             }
  34.             int[] array = new int[size];
  35.             System.out.println("Enter array elements");
  36.             int i;
  37.             for (i = 0; i < array.length; i++) {
  38.                 try {
  39.                     array[i] = Integer.parseInt(br.readLine());
  40.                 } catch (Exception e) {
  41.                     System.out.println("An error occurred");
  42.                     return;
  43.                 }
  44.             }
  45.             System.out.println("The initial array is");
  46.             for(i = 0;i < array.length; i++){
  47.                 System.out.print(array[i] + " ");
  48.             }
  49.             nextGreatest(array);
  50.             System.out.println("
    The final array is");
  51.             for(i = 0;i < array.length; i++){
  52.                 System.out.print(array[i] + " ");
  53.             }
  54.         }
  55. }
Program Explanation

1. In function nextGreatest(), the variable max is initialized to the last value in the array (int max=array[array.length-1]).
2. The loop for(i=array.length-1; i>=0; i–) traverses the array from right to left.
3. The element array[i] is stored in a variable temp and its value is changed to max.
4. The variable max is updated using the condition if(temp > max).
5. Finally, the last value in the array is set to zero.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
-1
-3
3
2
8
6
The initial array is
-1 -3 3 2 8 6 
The final array is
8 8 8 8 6 0
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
5
4
3
2
1
The initial array is
5 4 3 2 1 
The final array is
4 3 2 1 0

Search
Related Articles

Leave a Comment: