Replace Elements with Greatest Element on Right Side

Easy
488.

Replace Elements with Greatest Element on Right Side

Replace Elements with Greatest Element on Right Side is an easy coding problem on arrays, asked in Amazon and Google interviews.

Given an array arr, replace every element with the greatest element among the elements to its right, and replace the last element with -1.

Return the resulting array.

Example 1

Input
arr = [17,18,5,4,6,1]
Output
[18,6,6,6,1,-1]
Explanation
The largest value right of 17 is 18; right of 18 it is 6; and so on.

Example 2

Input
arr = [400]
Output
[-1]

Example 3

Input
arr = [1,2,3]
Output
[3,3,-1]

Constraints

  • 1 <= arr.length <= 10000
  • 1 <= arr[i] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Replace Elements with Greatest Element on Right Side Solution

Replace Elements with Greatest Element on Right Side solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Replace Elements with Greatest Element on Right Side is an easy coding problem on arrays, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array arr, replace every element with the greatest element among the elements to its right, and replace the last element with -1.

Return the resulting array.

Example 1

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation: The largest value right of 17 is 18; right of 18 it is 6; and so on.

Example 2

Input: arr = [400]
Output: [-1]

Example 3

Input: arr = [1,2,3]
Output: [3,3,-1]

Constraints

  • 1 <= arr.length <= 10000
  • 1 <= arr[i] <= 100000

Hints for Replace Elements with Greatest Element on Right Side

  1. Hint 1

    A nested loop recomputes the same suffix maximum over and over.

  2. Hint 2

    Walk the array from the right instead, carrying the maximum seen so far.

  3. Hint 3

    Write the current running maximum before folding arr[i] into it — the element itself is not part of its own answer.

How to solve Replace Elements with Greatest Element on Right Side

The answer at index i is the maximum of the suffix starting at i + 1. A single right-to-left pass keeps that value in one variable.

Approach

  1. Initialise best = -1, which is exactly the answer for the final position.
  2. Sweep i from n - 1 down to 0: write best into out[i] first.
  3. Then update best = max(best, arr[i]) so the next (more leftward) index sees the correct suffix maximum.

Why it works

Writing before updating is what excludes arr[i] from its own suffix. The invariant "best = max of arr[i+1..n-1]" holds at every write.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Updating best before writing includes the element itself and produces [18,18,6,6,6,1] on the first example.
  • Seeding best with arr[n-1] instead of -1 loses the required -1 in the last slot.
  • In-place rewriting works only if you keep the old arr[i] in a temporary before overwriting it.

Reference solution

Python

from typing import List

def replaceElements(arr: List[int]) -> List[int]:
    out = [0] * len(arr)
    best = -1
    for i in range(len(arr) - 1, -1, -1):
        out[i] = best
        if arr[i] > best:
            best = arr[i]
    return out

Java

public static int[] replaceElements(int[] arr) {
    int[] out = new int[arr.length];
    int best = -1;
    for (int i = arr.length - 1; i >= 0; i--) {
        out[i] = best;
        if (arr[i] > best) best = arr[i];
    }
    return out;
}

C++

vector<int> replaceElements(vector<int>& arr) {
    vector<int> out(arr.size(), 0);
    int best = -1;
    for (int i = (int) arr.size() - 1; i >= 0; i--) {
        out[i] = best;
        if (arr[i] > best) best = arr[i];
    }
    return out;
}

JavaScript

var replaceElements = function(arr) {
    const out = new Array(arr.length).fill(0);
    let best = -1;
    for (let i = arr.length - 1; i >= 0; i--) {
        out[i] = best;
        if (arr[i] > best) best = arr[i];
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays