Replace Elements with Greatest Element on Right Side solution and explanation
Google
9 more videos on this problem
Leetcode 1299 - REPLACE ELEMENTS WITH GREATEST ELEMENT ON RIGHT SIDENeetCode · 8:58 · 75K views
Replace Elements with Greatest Element on Right Side (Leetcode 1299)Coding Interviews · 6:56 · 1K views
LeetCode - 1299 Replace Elements with Greatest Element on Right Side | Arrays CardAditya Mahajan · 5:41 · 1K views
1299.1 Replace Elements with Greatest Element on Right Side(Theory)|#10 | Arrays Playlist | LeetcodeCTO Bhaiya · 7:07 · 1K views
1299. Replace Elements with Greatest Element on Right Side || easy question || c++ solutioncode Explainer · 3:30 · 1K views
REPLACE ELEMENTS WITH GREATEST ELEMENT ON RIGHT SIDE - Leetcode 1299 - C++ - بالعربيTech Time · 14:54 · 981 views
Leetcode 1299: Replace Elements with Greatest Element on Right SideAlgorithms Casts · 16:03 · 918 views
Replace Element with Greatest Element on Right Side | Leetcode 1299 | FAANG interview questionSuper Lazy Coder · 14:01 · 857 views
Leetcode Solution - 1299 Replace Elements with Greatest Element on Right SideJohn Leonardo · 2:44 · 765 views
1299 Replace Elements with Greatest Element on Right Side LeetСode ( Interview Question) JavaScriptdev alex · 4:14 · 752 views
The problem
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Example 1:
Input: arr = [17,18,5,4,6,1] Output: [18,6,6,6,1,-1] Explanation: - index 0 --> the greatest element to the right of index 0 is index 1 (18). - index 1 --> the greatest element to the right of index 1 is index 4 (6). - index 2 --> the greatest element to the right of index 2 is index 4 (6). - index 3 --> the greatest element to the right of index 3 is index 4 (6). - index 4 --> the greatest element to the right of index 4 is index 5 (1). - index 5 --> there are no elements to the right of index 5, so we put -1.
Example 2:
Input: arr = [400] Output: [-1] Explanation: There are no elements to the right of index 0.
Constraints:
1 <= arr.length <= 1041 <= arr[i] <= 105
Approach overview
Problem Overview: You are given an integer array arr. For every index, replace the value with the greatest element that appears to its right. The last element has no elements to its right, so it becomes -1. The goal is to compute the transformation efficiently.
Approach 1: Brute Force Approach (Time: O(n^2), Space: O(1))
For each index i, scan the subarray from i+1 to the end and compute the maximum value. Replace arr[i] with that maximum. The final element is set to -1. This method relies purely on repeated traversal of the array, making it straightforward to reason about but inefficient for large inputs.
The key drawback is repeated work. Every element recomputes the maximum of the suffix even though nearby elements share most of the same suffix values. That repeated scanning results in quadratic time complexity.
Approach 2: Reverse Iteration Approach (Time: O(n), Space: O(1))
The optimal solution processes the array from right to left while maintaining the maximum value seen so far. Start with maxRight = -1. For each index moving backward, store the current element, replace it with maxRight, then update maxRight = max(maxRight, originalValue).
This works because when you traverse from the end, maxRight always represents the largest element among all elements to the right of the current index. Each element is processed exactly once, and the algorithm only stores a single running maximum. The technique is common in array problems where suffix information is needed without extra memory.
The approach modifies the array in-place and avoids additional data structures. It behaves similarly to a suffix maximum computation often seen in prefix/suffix style array problems.
Recommended for interviews: Interviewers expect the reverse iteration solution. It shows you recognize that the maximum of the suffix can be maintained incrementally instead of recomputed. Starting with the brute force idea demonstrates understanding of the requirement, but transitioning to the O(n) reverse traversal shows strong optimization instincts in array manipulation problems.
Approach 1: Reverse Iteration Approach
This approach iterates over the array starting from the end toward the beginning. By doing so, we can keep a running track of the maximum element found so far on the right side. This method allows us to update each element in a single pass efficiently.
def replace_with_greatest(arr):
max_from_right = -1
for i in range(len(arr) - 1, -1, -1):
new_val = max_from_right
if arr[i] > max_from_right:
max_from_right = arr[i]
arr[i] = new_val
arr = [17, 18, 5, 4, 6, 1]
replace_with_greatest(arr)
print(arr)public class Solution {
public void replaceWithGreatest(int[] arr) {
int max_from_right = -1;
for (int i = arr.length - 1; i >= 0; i--) {
int new_val = max_from_right;
if (arr[i] > max_from_right) {
max_from_right = arr[i];
}
arr[i] = new_val;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {17, 18, 5, 4, 6, 1};
sol.replaceWithGreatest(arr);
for (int val : arr) {
System.out.print(val + " ");
}
}
}#include <iostream>
#include <vector>
void replaceWithGreatest(std::vector<int>& arr) {
int max_from_right = -1;
for (int i = arr.size() - 1; i >= 0; --i) {
int new_val = max_from_right;
if (arr[i] > max_from_right) {
max_from_right = arr[i];
}
arr[i] = new_val;
}
}
int main() {
std::vector<int> arr = {17, 18, 5, 4, 6, 1};
replaceWithGreatest(arr);
for (int val : arr) {
std::cout << val << " ";
}
return 0;
}function replaceWithGreatest(arr) {
let max_from_right = -1;
for (let i = arr.length - 1; i >= 0; i--) {
let new_val = max_from_right;
if (arr[i] > max_from_right) {
max_from_right = arr[i];
}
arr[i] = new_val;
}
return arr;
}
const arr = [17, 18, 5, 4, 6, 1];
console.log(replaceWithGreatest(arr));#include <stdio.h>
void replaceWithGreatest(int* arr, int arrSize) {
int max_from_right = -1;
for (int i = arrSize - 1; i >= 0; i--) {
int new_val = max_from_right;
if (arr[i] > max_from_right) {
max_from_right = arr[i];
}
arr[i] = new_val;
}
}
int main() {
int arr[] = {17,18,5,4,6,1};
int size = sizeof(arr) / sizeof(arr[0]);
replaceWithGreatest(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void ReplaceWithGreatest(int[] arr) {
int max_from_right = -1;
for (int i = arr.Length - 1; i >= 0; i--) {
int new_val = max_from_right;
if (arr[i] > max_from_right) {
max_from_right = arr[i];
}
arr[i] = new_val;
}
}
static void Main() {
Solution sol = new Solution();
int[] arr = {17, 18, 5, 4, 6, 1};
sol.ReplaceWithGreatest(arr);
Console.WriteLine(string.Join(" ", arr));
}
}In Python, the code iterates backwards through the array, replacing each value with the greatest value seen to the right so far, using a single extra variable to hold intermediate results.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Brute Force Approach
This approach involves nested loops, where for each element, we check its following elements to find the greatest and update it. Although this is not the most efficient approach, it's easier to understand.
def replace_with_greatest(arr):
for i in range(len(arr)):
max_from_right = -1
for j in range(i + 1, len(arr)):
if arr[j] > max_from_right:
max_from_right = arr[j]
arr[i] = max_from_right
arr = [17, 18, 5, 4, 6, 1]
replace_with_greatest(arr)
print(arr)public class Solution {
public void replaceWithGreatest(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int max_from_right = -1;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > max_from_right) {
max_from_right = arr[j];
}
}
arr[i] = max_from_right;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {17, 18, 5, 4, 6, 1};
sol.replaceWithGreatest(arr);
for (int val : arr) {
System.out.print(val + " ");
}
}
}#include <iostream>
#include <vector>
void replaceWithGreatest(std::vector<int>& arr) {
for (size_t i = 0; i < arr.size(); ++i) {
int max_from_right = -1;
for (size_t j = i + 1; j < arr.size(); ++j) {
if (arr[j] > max_from_right) {
max_from_right = arr[j];
}
}
arr[i] = max_from_right;
}
}
int main() {
std::vector<int> arr = {17, 18, 5, 4, 6, 1};
replaceWithGreatest(arr);
for (int val : arr) {
std::cout << val << " ";
}
return 0;
}function replaceWithGreatest(arr) {
for (let i = 0; i < arr.length; i++) {
let max_from_right = -1;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] > max_from_right) {
max_from_right = arr[j];
}
}
arr[i] = max_from_right;
}
return arr;
}
const arr = [17, 18, 5, 4, 6, 1];
console.log(replaceWithGreatest(arr));#include <stdio.h>
void replaceWithGreatest(int* arr, int arrSize) {
for (int i = 0; i < arrSize; i++) {
int max_from_right = -1;
for (int j = i + 1; j < arrSize; j++) {
if (arr[j] > max_from_right) {
max_from_right = arr[j];
}
}
arr[i] = max_from_right;
}
}
int main() {
int arr[] = {17,18,5,4,6,1};
int size = sizeof(arr) / sizeof(arr[0]);
replaceWithGreatest(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void ReplaceWithGreatest(int[] arr) {
for (int i = 0; i < arr.Length; i++) {
int max_from_right = -1;
for (int j = i + 1; j < arr.Length; j++) {
if (arr[j] > max_from_right) {
max_from_right = arr[j];
}
}
arr[i] = max_from_right;
}
}
static void Main() {
Solution sol = new Solution();
int[] arr = {17, 18, 5, 4, 6, 1};
sol.ReplaceWithGreatest(arr);
Console.WriteLine(string.Join(" ", arr));
}
}Python code leverages a double loop to iterate and replace every array element with the maximal value of its following subsequences, illustrating a brute-force solution.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 3: Reverse Traversal
We use a variable mx to record the maximum value to the right of the current position, initially mx = -1.
Then we traverse the array from right to left. For each position i, we denote the current value as x, update the current position's value to mx, and then update mx = max(mx, x).
Finally, return the original array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function replaceElements(arr: number[]): number[] {
for (let i = arr.length - 1, mx = -1; ~i; --i) {
const x = arr[i];
arr[i] = mx;
mx = Math.max(mx, x);
}
return arr;
}func replaceElements(arr []int) []int {
for i, mx := len(arr)-1, -1; i >= 0; i-- {
x := arr[i]
arr[i] = mx
mx = max(mx, x)
}
return arr
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Iteration Approach | Time Complexity: O(n) |
| Brute Force Approach | Time Complexity: O(n^2) |
| Reverse Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Approach | O(n^2) | O(1) | Useful for understanding the problem or when constraints are very small. |
| Reverse Iteration Approach | O(n) | O(1) | Best choice for interviews and production. Maintains a running suffix maximum while traversing from right to left. |
Frequently asked questions
Is Replace Elements with Greatest Element on Right Side easy or hard?
The problem is categorized as Easy because it mainly tests array traversal and recognizing a suffix maximum pattern. Once you realize that scanning from the right avoids repeated work, the implementation becomes a short linear pass.
Replace Elements with Greatest Element on Right Side Python/Java solution
The typical Python or Java solution iterates from the last index to the first while maintaining a maxRight variable. At each step, the element is replaced with maxRight and the variable is updated with the maximum of the current element and maxRight. This results in O(n) time and constant space.
How to solve Replace Elements with Greatest Element on Right Side in O(n)?
Traverse the array from right to left while keeping a variable called maxRight. Replace the current element with maxRight, then update maxRight using the original value of that element. This maintains the maximum of all elements to the right without rescanning the array.
What is the best approach for Replace Elements with Greatest Element on Right Side?
The best approach is reverse iteration from the end of the array while maintaining the maximum value seen so far. For each index, replace the current element with the stored maximum and then update the maximum if the current element is larger. This processes each element once, resulting in O(n) time and O(1) extra space.
Is Replace Elements with Greatest Element on Right Side asked at Google/Amazon/Meta?
Array transformation and suffix maximum problems appear frequently in interviews at companies like Amazon and Google. While this exact question may not always appear verbatim, the reverse traversal and running maximum pattern is commonly tested in coding interviews.
What data structure is used in Replace Elements with Greatest Element on Right Side?
The problem primarily uses a simple array with a running variable to track the suffix maximum. No additional data structures like stacks or hash maps are required in the optimal solution, which keeps the space complexity at O(1).
What is the time complexity of Replace Elements with Greatest Element on Right Side?
The optimal solution runs in O(n) time because the array is traversed exactly once from right to left. A running variable stores the maximum value seen so far. The brute force approach takes O(n^2) time since it scans the remaining elements for every index.