Code Logo

Replace Elements with Greatest Element on Right Side

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given an array arr, replace every element with the greatest element among the elements to its right. The rightmost element should be replaced with -1 since there are no elements to its right. Return the modified array.

This is a classic right-to-left DP problem. Start from the end of the array, tracking the maximum value seen so far. For each position from right to left, store the current max in the result, then update the max with the current element if it is larger.

The DP recurrence is: for i from n-1 down to 0, result[i] = maxSoFar, then update maxSoFar = max(maxSoFar, arr[i]). This processes each element once in O(n) time with O(1) extra space.

Edge cases include a single element (return [-1]), an empty array (return []), and all elements equal (all become the same value).

The right-to-left DP pattern is used when each element's value depends on future elements. By iterating backwards, we naturally encounter the dependent elements before the dependent ones. This is similar to how DP solves problems by computing subproblems in dependency order.

This right-to-left DP pattern is widely applicable in computing next greater elements, stock span, and any scenario where future values influence current decisions. The single scalar state variable captures all necessary future information efficiently.

Example Input & Output

Example 1
Input
[5,4,3,2,1]
Output
[4,3,2,1,-1]
Explanation

Descending.

Example 2
Input
[]
Output
[]
Explanation

Empty.

Example 3
Input
[1]
Output
[-1]
Explanation

Single element.

Example 4
Input
[17,18,5,4,6,1]
Output
[18,6,6,6,1,-1]
Explanation

18 > 17, 6 > rest, 1 -> -1.

Example 5
Input
[1,2,3,4]
Output
[4,4,4,4,-1]
Explanation

Ascending, max is last.

Algorithm Flow

Recommendation Algorithm Flow for Replace Elements with Greatest Element on Right Side

Solution Approach

Replace each element in an array with the greatest element among the elements to its right, and replace the last element with -1. Iterate from right to left, tracking the maximum seen so far. For each position, store the current maximum (which represents the max to the right), then update the maximum if the current element is larger.

function replaceElements(arr) {
  var maxRight = -1;
  for (var i = arr.length - 1; i >= 0; i--) {
    var cur = arr[i];
    arr[i] = maxRight;
    if (cur > maxRight) maxRight = cur;
  }
  return arr;
}

Right-to-left traversal naturally gives access to the greatest element on the right. The variable maxRight starts at -1 (for the last element) and is updated as we move leftward. Each element is replaced before the maxRight update so the current element does not influence its own replacement.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        int m=-1;
        for (int i=arr.length-1;i>=0;i--) {
            int c=arr[i];
            arr[i]=m;
            if (c>m) m=c;
        }
        return arr;
    }
}