Replace Elements with Greatest Element on Right Side

Share

Given an array nums, 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:
For index 0 - largest element to right side from idex 0 is 18.
For index 1 - largest element to right side from idex 1 is 6.
For index 2 - largest element to right side from idex 2 is 6.
For index 3 - largest element to right side from idex 3 is 6.
For index 4 - largest element to right side from idex 4 is 1.
For index 5 - last element should be replaced with -1.
Example 2
Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Contents

Solution 1 - using brute force approach

In this approach, for every number at index i, we will check all remaining numbers to the right of the array starting from i to n and get maximum number, then place that at index i. Finally when we are at end index of array just put -1 as per problem statement.

Java
public class ReplaceElementsWithGreatestFromRight {

    /* brute force approach */
    static int[] usingBruteForce(int[] nums) {
        int[] ans = new int[nums.length];
        for(int i=0; i<nums.length-1; i++) {
            int greatest = 0;
            for(int j=i+1; j<nums.length; j++) {
                if(nums[j]>greatest) {
                    greatest = nums[j];
                }
            }
            nums[i] = greatest;
        }

        nums[nums.length -1] = -1;
        return nums;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n2) time where n is the length of nums array, this is because we are looping through nums array in a nested for loop.
Space complexity: O(n) for the ans array or O(1) if you are allowed to modify input array and then return that as answer.

Solution 2 - start copying largest elements from right side

In this approach, we are going to start from the right end of nums array, first put -1 at the end. Thereafter, compare the maximum between the elements from ans array at i+1 index and nums array at i+1 index.

Code
ans[i] = MAX(ans[i+1], nums[i+1]);
The reason we do this is because:
  • When we are at index i+1 in nums array ans array holds maximum value up until i+2 index.
  • When we are at index i in nums array ans array holds maximum value up until i+1 index.
So, ans always holds maximum up until one index after current index and when move index to the left side, we need look into maximum element so far from ans array, then next element from nums array.

Let's look at below diagram for input nums= {17, 18, 5, 4, 6, 1}

Copy from right side
Java
public class ReplaceElementsWithGreatestFromRight {

    /* we start copying largest from right side*/
    static int[] copyLargestFromRightSide(int[] nums) {
        int[] ans = new int[nums.length];
        ans[nums.length -1] = -1;
        for(int i=nums.length-2; i>=0; i--) {
            ans[i] = Math.max(nums[i+1], ans[i+1]);
        }
        return ans;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array since we are looping through input array only once.
Space complexity: O(n) for the ans array.

Full source code on GitHub