LeetCode Problem - Link


Problem

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]



Bruteforce Solution

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function(arr) {
    for(let i=0;i<arr.length-1;i++){
        let max = arr[i+1]
        for(let j=i+1; j<arr.length; j++){
            if(arr[j] > max){
                max = arr[j]
            }
        }
        arr[i] = max;
    }


    // replace last element
    arr[arr.length-1] = -1
    return arr


};


Single Loop O(N) Solution

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function (arr) {
    var max = arr[arr.length - 1]
    arr[arr.length - 1] = -1


    for (let i = arr.length - 2; i >= 0; i--) {
        let current_val = arr[i]
        arr[i] = max
        if (current_val > max) {
            max = current_val
        }
    }


    return arr
};