Replace Each Element with the Maximum Element to Its Right
Solve this ProblemEasy10–15 min
Topics
Array
Companies
AmazonMicrosoftAdobe
Given an array
nums, return a new array where every element is replaced by the greatest value found anywhere to its right. The very last position has nothing to its right, so it always becomes -1.
Scanning right-to-left while keeping track of the biggest value seen so far avoids re-scanning the remaining array at every position.
Test Case 1:
Input:nums = [9, 4, 6, 2, 8]
Output:[8, 8, 8, 8, -1]
Explanation:8 is the biggest value to the right of every position except the last.
Test Case 2:
Input:nums = [1, 2]
Output:[2, -1]
Explanation:1 has only 2 to its right, so it becomes 2; 2 is last, with nothing to its right, so it becomes -1.
Test Case 3:
Input:nums = [7, 7, 7]
Output:[7, 7, -1]
Explanation:Ties still count — the greatest value to the right can equal the element itself.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹ - ◆
The last position in the result is always -1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int[] replaceWithGreatestOnRight(int[] nums) { |
| 3 | int n = nums.length; |
| 4 | int[] result = new int[n]; |
| 5 | int maxSoFar = -1; |
| 6 | for (int i = n - 1; i >= 0; i--) { |
| 7 | result[i] = maxSoFar; |
| 8 | if (nums[i] > maxSoFar) maxSoFar = nums[i]; |
| 9 | } |
| 10 | return result; |
| 11 | } |
| 12 | } |
| 13 |
Array
9
4
6
2
8
0
1
2
3
4
Array
_
_
_
_
_
0
1
2
3
4
Variables
maxSoFar
-1INITIALIZE
Start scanning from the right. maxSoFar begins at -1 since there's nothing to the right of the last element.
Step 1 / 7
Approach & Solutions
Brute Force — Scan Right for Every Position
BruteFor each index, scan every element after it to find the maximum, and use -1 if there's nothing to the right. Straightforward, but re-scanning the remaining array for every single position adds up fast on large inputs.
Time
O(n²)Space
O(n)Java
1class Solution {
2 public int[] replaceWithGreatestOnRight(int[] nums) {
3 int n = nums.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 int maxRight = -1;
7 for (int j = i + 1; j < n; j++) {
8 maxRight = Math.max(maxRight, nums[j]);
9 }
10 result[i] = maxRight;
11 }
12 return result;
13 }
14}Optimal — Traverse Right to Left
OptimalWalk the array backwards while tracking the largest value seen so far. At each position, first record that running max as the answer for this index, then update the running max with the current element — that way the current value is never counted as being "to the right of itself".
Time
O(n)Space
O(n)Java
1class Solution {
2 public int[] replaceWithGreatestOnRight(int[] nums) {
3 int n = nums.length;
4 int[] result = new int[n];
5 int maxSoFar = -1;
6 for (int i = n - 1; i >= 0; i--) {
7 result[i] = maxSoFar;
8 if (nums[i] > maxSoFar) maxSoFar = nums[i];
9 }
10 return result;
11 }
12}