Introduction

This array problem asks you to replace each element with the greatest element that appears to its right. It is a good example of how direction matters in algorithm design, because the efficient solution comes from scanning the array backward rather than restarting a search for every position.

Problem Statement

Given an array, replace each value with the maximum value among the elements to its right. The last element has no right-side elements, so it is usually replaced with -1.

Example:

[16, 17, 4, 3, 5, 2]

becomes:

[17, 5, 5, 5, 2, -1]

The Naive Approach

The most direct solution is:

• for each index
• scan everything to the right
• compute the maximum

That works, but it costs O(n^2) time.

1def replace_with_right_max_slow(arr):
2    result = []
3    for i in range(len(arr)):
4        if i == len(arr) - 1:
5            result.append(-1)
6        else:
7            result.append(max(arr[i + 1:]))
8    return result
9
10
11print(replace_with_right_max_slow([16, 17, 4, 3, 5, 2]))

For small arrays this is fine, but it becomes wasteful because the same suffixes are examined repeatedly.

The Efficient Right-to-Left Solution

The key observation is that when you move from right to left, you can keep track of the maximum element seen so far.

Algorithm:

1. Start from the last element.
2. Keep a variable named max_right.
3. Replace the current element with max_right.
4. Update max_right if the original element was larger.

This reduces the runtime to O(n) and uses O(1) extra space if you modify the array in place.

1def replace_with_right_max(arr):
2    max_right = -1
3
4    for i in range(len(arr) - 1, -1, -1):
5        current = arr[i]
6        arr[i] = max_right
7        if current > max_right:
8            max_right = current
9
10    return arr
11
12
13data = [16, 17, 4, 3, 5, 2]
14print(replace_with_right_max(data))

Output:

[17, 5, 5, 5, 2, -1]

Why the Backward Scan Works

By the time you reach index i, max_right already holds the maximum value from the suffix to the right of i. That means you never need to rescan that suffix.

Walking through the example:

• start at 2, replace with -1, now max_right = 2
• at 5, replace with 2, now max_right = 5
• at 3, replace with 5, keep max_right = 5
• at 4, replace with 5, keep max_right = 5
• at 17, replace with 5, now max_right = 17
• at 16, replace with 17

The result is produced in one pass.

Java Version

The same idea works cleanly in Java:

1import java.util.Arrays;
2
3public class RightMax {
4    public static void replaceWithRightMax(int[] arr) {
5        int maxRight = -1;
6
7        for (int i = arr.length - 1; i >= 0; i--) {
8            int current = arr[i];
9            arr[i] = maxRight;
10            if (current > maxRight) {
11                maxRight = current;
12            }
13        }
14    }
15
16    public static void main(String[] args) {
17        int[] arr = {16, 17, 4, 3, 5, 2};
18        replaceWithRightMax(arr);
19        System.out.println(Arrays.toString(arr));
20    }
21}

Common Pitfalls

The most common mistake is updating max_right before saving the current element. If you overwrite the value too early, you lose the data needed to compute the next maximum correctly.

Another issue is forgetting the last-element rule. The final position has no elements on its right, so you must choose the agreed sentinel value such as -1.

A third pitfall is assuming -1 is always safe. If the array can contain negative values, -1 may not be semantically appropriate. In that case, define the output rule clearly or return a separate result array with a different marker.

Finally, some developers use extra arrays when in-place modification is acceptable. That is not wrong, but it increases memory use unnecessarily for this problem.

Summary

• The efficient solution scans the array from right to left.
• Keep a running maximum of the elements already seen on the right.
• The optimized algorithm runs in O(n) time.
• You can solve the problem in place with O(1) extra space.
• Be explicit about the sentinel value for the last element, especially with negative inputs.