Java Program to Replace Elements with Greatest Element on Right Side

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
advertisement
advertisement

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("\nThe 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

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.