Replace Elements with Greatest Element on Right Side

How it works

By traversing right to left, we can maintain a running maximum of all elements seen so far in rightMax. When we visit position i, the current running maximum represents the greatest element to the right of i. We then update rightMax to include arr[i] for the next iteration. This eliminates redundant scanning.

Steps

1. Create a result array ans of the same size as the input.
2. Initialize rightMax to -1 (the value for the last position).
3. Traverse the array from right to left using index i.
4. For each index i, store the current rightMax in ans.
5. Update rightMax to be the maximum of itself and arr[i].
6. Return the ans array.

Complexity

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

The output array is not counted towards space complexity, as the standard convention measures only auxiliary working space.

Things to watch for

Traversing Left to Right

Processing the array from left to right requires recalculating the maximum of all right elements for each position, resulting in O(n^2) time complexity. The optimal approach traverses right to left, maintaining a running maximum in a single pass.

Updating the Maximum Before Storing the Result

When traversing right to left, the current element's value must be stored in the result before updating rightMax. Updating rightMax first causes the current element to incorrectly include itself in its own replacement value.

from typing import List

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = [0] * n
        rightMax = -1
        for i in range(n - 1, -1, -1):
            ans[i] = rightMax
            rightMax = max(arr[i], rightMax)
        return ans

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