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:

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

Example 2:

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

Constraints:

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5

Solution

Although this problem looks like sorting, it’s not exactly. In this case, we can start iterating from the right and keep track of the max number seen so far in a variable. This is the value we have to insert at each stage in the iteration. So, the problem becomes trivial with single iteration through the array. The important point is that we have start iterating from the end and not from the beginning.

 1class Solution {
 2    public int[] replaceElements(int[] arr) {
 3        int maxSoFar = -1, index = arr.length - 1;
 4        while (index >= 0) {
 5            int temp = arr[index];
 6            arr[index--] = maxSoFar;
 7            maxSoFar = Math.max(maxSoFar, temp);
 8        }
 9        return arr;
10    }
11}