Replace every element with the next greatest

Question:

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it with -1. For example, if the array is {16, 17, 4, 3, 5, 2}, then it should be modified to {17, 5, 5, 5, 2, -1}.

Solution1:

A naive method is to run two loops. The outer loop will one by one pick array elements from left to right. The inner loop will find the greatest element present after the picked element. Finally the outer loop will replace the picked element with the greatest element found by inner loop. The time complexity of this method will be O(n*n).

Solution2:

A better approach is to replace all elements using one traversal of the array. The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element. The time complexity of this method will be O(n).

public int[] ReplaceNextGreatest(int[] a) {

           int len = a.length;

           int maxNum=a[len-1];

           // Replace right most number with -1

           a[len-1]=-1;

           for(int i=len-2; i>=0; i--) {             

                int temp = a[i];

                a[i] = maxNum;

                if(temp>maxNum) {

                     maxNum = temp;

                }

           }

           return a;

}