Leetcode 1299: Replace Elements with Greatest Element on Right Side

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

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]

Constraints:

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

Solution 1: two loops

var replaceElements = function(arr) {
    let newArr = []
    for(let i=0; i<arr.length; i++){    
        let max = arr[i+1]
        for(let j=i+1;j<arr.length;j++){
            let value = arr[j+1]
        max = value > max? value: max
        }
        newArr.push(max)
    }
    newArr[arr.length-1] = -1
    return newArr
};

Time complexity : O(n²)
Space complexity : O(n)

Solution 2: One loop

With last index as -1, we can 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.

For example:

let arr = [17,18,5,4,6,1]

and as we know:

1. newArr[5] is -1
2. newArr[4] is equal to arr[5]
3. newArr[3] is equal to the maximum number among arr[4] to arr[5]. This is also equal to the maximum number among arr[4] to newArr[4]

To simplify the logic, we can describe like this:

newArr[0] = max(arr[1:5]) = max(arr[1], newArr[1])
newArr[1] = max(arr[2:5]) = max(arr[2], newArr[2])
newArr[2] = max(arr[3:5]) = max(arr[3], newArr[3])
newArr[3] = max(arr[4:5]) = max(arr[4], newArr[4])
newArr[4] = arr[5]
newArr[5] = -1

And the solution will be:

var replaceElements = function(arr) {
    let newArr = [];
    newArr[arr.length-1] = -1;
    for (i = arr.length-2; i >= 0; i--) {
        newArr[i] = Math.max(newArr[i+1],arr[i+1]);
    }
    return newArr;
};

Time complexity : O(n)
Space complexity : O(n)

Comments

[Azeez Abiodun Solomon]

Thanks

[Tsuifei Pommier]

Thanks Kira, explained very clearly :D