Code Logo

Replace Elements with Greatest Element on Right Side

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Replace Elements with Greatest Element on Right Side

Solution Approach

Iterate right-to-left, tracking max seen. Replace each element with current max, then update max.

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

Time O(n), Space 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;
    }
}