Replace Elements with Greatest Element on Right Side in Java

Replace Elements with Greatest Element on Right Side Leetcode Solution in Java

Problem Description :-

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation: 
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

So, lets see solution of above problem.

Solution 1

class Solution {
    
    public int[] replaceElements(int[] array) {
    
        int max = -1;
        
        //Loop from right to left
        for (int i = array.length-1; i >= 0; i--) {
            
            // Getting current value 
            int current = array[i];
            array[i] = max;
            
            // If current value is greater than max,  
            // then store current array value to max variable.
            if (current > max) {
                max = current;
            }
        }
        return array;
    }
}

Explanation :-

array = [17, 18, 5, 4, 6, 1]

• Define max variable with -1. So we can put -1 at last index of array. (As per problem solution).
• Traverse array from Right to Left using for loop.
• i = 5
• Getting current array index value. 
• current = 1.
• Add max variable value to array current index.
• array[5] = -1.
• array = [17, 18, 5, 4, 6, -1].
• Checking if condition | current > max
  
• 1 > -1 becomes true
• Store current value to max variable.
• max = 1 
  
•  i = 4, array = [17, 18, 5, 4, 6, -1], max = 1, current = 1.
• current = 6.
• array[4] = 1.
• 6 > 1 becomes true. | max = 6.
  
•  i = 3, array = [17, 18, 5, 4, 1, -1], max = 6, current = 6.
• current = 4.
• array[3] = 6.
• 4 > 6 becomes false.
•  i = 2, array = [17, 18, 5, 6, 1, -1], max = 6, current = 4.
• current = 5.
• array[2] = 6.
• 5 > 6 becomes false.
•  i = 1, array = [17, 18, 6, 6, 1, -1], max = 6, current = 5.
• current = 18.
• array[1] = 6.
• 18 > 6 becomes true. | max = 18.
  
•  i = 0, array = [17, 6, 6, 6, 1, -1], max = 18, current = 18.
• current = 17.
• array[0] = 18.
• 18 > 17 becomes false.
•  array = [18, 6, 6, 6, 1, -1].

Solution 2  

class Solution {
    
    public int[] replaceElements(int[] array) {
    
        for (int i = 0; i < array.length-1; i++) {
            int max = 0;
            for (int j = i+1; j < array.length; j++) {
                
                if (array[j] > max){
                    max = array[j];
                }
            }
            array[i] = max;
        }

        array[array.length-1] = -1;

        return array;    
    }
}       

Explanation :-

• Traverse array from left to right using for loop.
• Traverse array from left to right using for loop. Start array from outer index + 1 (i + 1).
• Check if inner array value is greater than max value or not. If it is greater then, put array[j] value into max.
• After end of inner loop, put max value in current outer index.
• At last, put -1 into last array index. (As per problem description).
• Return array.

Happy Coding.

Other articles you may like :-

• Valid Mountain Array Leetcode solution in Java