// O(n^2) Solution: The Naive Approach

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


// O(n) Solution
class Solution {
    public int[] replaceElements(int[] arr) {
        int i, L = arr.length-1;
        int max = arr[L];
        for(i = L-1; i >= 0; i--){
            int temp = max;
            if(arr[i] >= max)
                max = arr[i];
            arr[i] = temp;
        }
        arr[L] = -1;
        return arr;
    }
}