Replace Elements with Greatest Element on Right Side

easy array suffix max

Problem

You are given an integer array arr. Replace every element with the greatest value that appears among the elements strictly to its right, and replace the last element with -1 because nothing lies to its right. Return the modified array (length up to 10⁴, values between 1 and 10⁵).

Inputarr = [17, 18, 5, 4, 6, 1]

Output[18, 6, 6, 6, 1, -1]

To the right of 17 the largest value is 18, to the right of 5 it is 6, and the last slot gets −1.

arr (comma-separated integers)

def replace_elements(arr):
    mx = -1                       # greatest value seen on the right
    for i in range(len(arr) - 1, -1, -1):
        cur = arr[i]              # stash the original value
        arr[i] = mx               # overwrite with the suffix max
        mx = max(mx, cur)         # fold the stash into the max
    return arr

function replaceElements(arr) {
  let mx = -1;                    // greatest value seen on the right
  for (let i = arr.length - 1; i >= 0; i--) {
    const cur = arr[i];           // stash the original value
    arr[i] = mx;                  // overwrite with the suffix max
    mx = Math.max(mx, cur);       // fold the stash into the max
  }
  return arr;
}

int[] replaceElements(int[] arr) {
    int mx = -1;                  // greatest value seen on the right
    for (int i = arr.length - 1; i >= 0; i--) {
        int cur = arr[i];         // stash the original value
        arr[i] = mx;              // overwrite with the suffix max
        mx = Math.max(mx, cur);   // fold the stash into the max
    }
    return arr;
}

vector<int> replaceElements(vector<int>& arr) {
    int mx = -1;                  // greatest value seen on the right
    for (int i = (int)arr.size() - 1; i >= 0; i--) {
        int cur = arr[i];         // stash the original value
        arr[i] = mx;              // overwrite with the suffix max
        mx = max(mx, cur);        // fold the stash into the max
    }
    return arr;
}

Explanation

The brute-force answer rescans everything to the right of each index, costing O(n²). The key insight is that the value we want at index i is exactly the suffix maximum of arr[i+1..n-1] — and suffix maxima can be built incrementally if we walk the array from right to left.

Keep one variable mx, the greatest value seen so far during the sweep, initialized to -1. At each index we do three tiny moves: stash the current value in cur, overwrite arr[i] with mx (the largest thing to its right), then update mx = max(mx, cur) so the value we just erased still counts for the elements further left.

Starting mx at -1 elegantly handles the edge case: when we visit the last index nothing has been seen yet, so it gets overwritten with -1, exactly what the problem demands.

Walk the default example [17, 18, 5, 4, 6, 1]. At i=5 we write −1 and remember 1; at i=4 we write 1 and raise mx to 6; at i=3, i=2, and i=1 we write 6 each time (6 stays the biggest until 18 is folded in at i=1); finally at i=0 we write 18. The array becomes [18, 6, 6, 6, 1, -1].

Each index is visited exactly once and only constant work happens per visit, so the time is O(n). Because we overwrite the array in place and carry just mx and cur, the extra space is O(1).

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