Replace Elements with Greatest Element on Right Side

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.

---

So, how can we solve this problem?

Approach 1: Using built-in functions in JavaScript

1. Initialize an empty array result.

2. Iterate through the input array, except the last element. We don’t need to check the last element since it will always be replaced with -1.

3. For each index i of the loop in the input array set the result[i] to the next maximum element on the right.

4. The next maximum is found using Math.max(), .slice() and ... (spread operator).

// ES6 Arrow Function
const replaceMaxRight = arr => {
    const result = [];

    for(let i = 0; i < arr.length; i++) {
        result[i] = Math.max(...arr.slice(i+1));
    }

    result[result.length - 1] = -1;

    return result;
}

Time Complexity: O(N²)

Space Complexity: O(N)

---

Note: Although the previous solution works, it is not the most efficient since its time complexity is O(N²). However, we can improve the time complexity to O(N) by iterating through the array from right to left. Let’s see this in our second approach to solve this problem.

Approach 2: Iterating the input array right-to-left

1. Initialize a variable called max to -1. This variable will keep track of the maximum element encountered so far.

2. Iterate the input array arr from the rightmost element because we want to keep track of the maximum element encountered so far from the right side.

3. For each iteration initialize a variable and store the value of the element at the current index arr[i] to this variable.

4. Then, we’ll set the value of the current index in the input array arr[i] to the maximum value we have seen so far, which is stored in the max variable.

5. Finally, we’ll update the max variable's value by comparing the current maximum value to the value we stored in Step 3. If the value we stored is greater than the current maximum value, we’ll update the max variable accordingly.

// ES6 Arrow Functions
const replaceMaxRight = arr => {
    let max = -1;

    for(let i = arr.length - 1; i >= 0; i--) {
        let curr = arr[i];
        arr[i] = max;
        max = Math.max(max, curr);
    }

    return arr;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

Note: Another way to code the problem that differs slightly from the second approach.

// ES6 Arrow Function
const replaceMaxRight = arr => {
    let max = arr[arr.length - 1];
    arr[arr.length - 1] = -1;

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

    return arr;
}

Note: Time and Space complexity remains the same as approach 2.

---

I hope this article has provided you with valuable insights and helped you better understand the different approaches to solve this problem. Happy coding!

---

Problem - Leetcode 1299