Back to solutions

Replace Elements With Greatest Element On Right Side

EasyArrays

Replace each element with the largest value to its right; last becomes -1.

Open problem
Constraints
  • 1 <= n <= 10^4
  • 1 <= nums[i] <= 10^5

Suffix maximum from the right

Time O(n)Space O(1)

Scan from the right keeping the greatest value seen so far (starting at -1 for the empty right side). At each index, remember the current value, overwrite the slot with the running max, then update the max with the value you saved. One pass and no extra array.

Key terms
suffix maximum:
The largest value among all elements from a position to the end.
running max:
The maximum seen so far while scanning, updated each step.
vector<int> replaceElements(vector<int>& nums) {
    int best = -1;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int cur = nums[i];
        nums[i] = best;
        best = max(best, cur);
    }
    return nums;
}
Step by step
  1. Start best = -1 (nothing to the right of the last element).
  2. Walk i from the last index down to 0.
  3. Save cur = nums[i]; set nums[i] = best (the greatest to its right).
  4. Update best = max(best, cur) so it covers this index for the next step.