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 <= 100001 <= arr[i] <= 100000
Hints for Replace Elements with Greatest Element on Right Side
Hint 1
A nested loop recomputes the same suffix maximum over and over.
Hint 2
Walk the array from the right instead, carrying the maximum seen so far.
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
- Initialise
best = -1, which is exactly the answer for the final position. - Sweep
ifromn - 1down to0: writebestintoout[i]first. - 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
bestbefore writing includes the element itself and produces[18,18,6,6,6,1]on the first example. - Seeding
bestwitharr[n-1]instead of-1loses the required-1in 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 outJava
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