Problem Description

You are given an array of integers arr. Your task is to replace every element in the array with the greatest element among the elements to its right. For the last element, replace it with -1 because there is no element to its right.

• For each index i (except the last), set arr[i] to the maximum value among arr[i+1], arr[i+2], ..., arr[n-1].
• For the last element arr[n-1], set it to -1.

Constraints:

• 1 ≤ arr.length ≤ 10⁴
• 1 ≤ arr[i] ≤ 10⁵

Thought Process

At first glance, the problem seems to require examining all elements to the right of each index to find the maximum. This would mean, for each element, running a loop through the rest of the array, which would be slow for large arrays.

However, we notice that as we move from right to left, we can keep track of the maximum value we've seen so far. This way, instead of repeatedly scanning the right part of the array for every element, we can update the maximum in constant time and fill the array efficiently.

This approach is much faster and uses only a small amount of extra space (just a variable to store the current maximum).

Solution Approach

• Step 1: Start from the end of the array and move backwards (right to left).
• Step 2: Initialize a variable, say max_so_far, to -1. This will hold the greatest value to the right as we iterate.
• Step 3: For each element from the last to the first:
  • Store the current value in a temporary variable (since we need it to update max_so_far after replacement).
  • Replace the current element with max_so_far.
  • Update max_so_far to be the maximum of its current value and the value from the temporary variable.
• Step 4: Continue this process until the start of the array is reached.

This method efficiently replaces each element with the greatest element to its right in a single pass, and only uses constant extra space.

Example Walkthrough

Let's walk through an example with arr = [17, 18, 5, 4, 6, 1]:

1. Start with max_so_far = -1.
2. Index 5 (value 1): Replace with -1, update max_so_far = max(-1, 1) = 1.
   Array: [17, 18, 5, 4, 6, -1]
3. Index 4 (value 6): Replace with 1, update max_so_far = max(1, 6) = 6.
   Array: [17, 18, 5, 4, 1, -1]
4. Index 3 (value 4): Replace with 6, update max_so_far = max(6, 4) = 6.
   Array: [17, 18, 5, 6, 1, -1]
5. Index 2 (value 5): Replace with 6, update max_so_far = max(6, 5) = 6.
   Array: [17, 18, 6, 6, 1, -1]
6. Index 1 (value 18): Replace with 6, update max_so_far = max(6, 18) = 18.
   Array: [17, 6, 6, 6, 1, -1]
7. Index 0 (value 17): Replace with 18, update max_so_far = max(18, 17) = 18.
   Array: [18, 6, 6, 6, 1, -1]

Final output: [18, 6, 6, 6, 1, -1]

Code Implementation

class Solution:
    def replaceElements(self, arr):
        max_so_far = -1
        for i in range(len(arr) - 1, -1, -1):
            current = arr[i]
            arr[i] = max_so_far
            max_so_far = max(max_so_far, current)
        return arr
      

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int max_so_far = -1;
        for (int i = arr.size() - 1; i >= 0; --i) {
            int current = arr[i];
            arr[i] = max_so_far;
            max_so_far = max(max_so_far, current);
        }
        return arr;
    }
};
      

class Solution {
    public int[] replaceElements(int[] arr) {
        int maxSoFar = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            int current = arr[i];
            arr[i] = maxSoFar;
            maxSoFar = Math.max(maxSoFar, current);
        }
        return arr;
    }
}
      

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

Time and Space Complexity

• Brute-force Approach: For each element, scan all elements to its right to find the maximum. This results in O(n²) time complexity, where n is the length of the array. Space complexity is O(1) if done in place.
• Optimized Approach: By traversing the array from right to left and keeping track of the maximum so far, each element is visited once. Thus, the time complexity is O(n). Only a single extra variable is used, so space complexity remains O(1).

The optimized approach is efficient and suitable even for large arrays.

Summary

The key insight in this problem is to realize that you can efficiently compute the greatest element to the right by traversing the array from the end, updating a running maximum. This approach avoids redundant work and achieves O(n) time with O(1) extra space, making it both simple and elegant.