Replace Elements with Greatest Element on Right Side: Right-to-Left Scan

Given an array arr, replace every element with the greatest element among the elements to its right, and replace the last element with -1. This is LeetCode 1299: Replace Elements with Greatest Element on Right Side.

For example, given arr = [17, 18, 5, 4, 6, 1], the result is [18, 6, 6, 6, 1, -1]. The element at index 0 becomes 18 because max(18, 5, 4, 6, 1) = 18. The last element always becomes -1 because there is nothing to its right.

Why this problem matters

This problem teaches two patterns that come up constantly in array problems. First, it shows that scanning right to left can be much more efficient than scanning left to right. Second, it demonstrates how a running maximum lets you avoid recomputing the same information at each position. Both ideas appear in harder problems like Product of Array Except Self and Daily Temperatures.

If you try to solve this left to right, you would need to scan the rest of the array at each position to find the maximum, giving you O(n^2) time. Flipping the direction and maintaining a running value drops that to O(n).

The key insight

Traverse the array from right to left. At each position, you already know the maximum of everything to the right because you have been tracking it as a running maximum. So the answer at the current position is simply the current running max. After recording that answer, update the running max with the original value at this position (in case it is larger than anything you have seen so far).

The last element is a special case: its answer is always -1, and its value becomes the initial running maximum.

The solution

def replace_elements(arr):
    n = len(arr)
    running_max = -1

    for i in range(n - 1, -1, -1):
        new_max = max(running_max, arr[i])
        arr[i] = running_max
        running_max = new_max

    return arr

The loop walks from the last index to the first. At each step, it saves the new running max (the greater of the current running max and the original value at arr[i]), then overwrites arr[i] with the old running max (which represents the greatest element to its right). Finally, it updates the running max for the next iteration.

The variable running_max starts at -1, which is the correct answer for the last element. On the first iteration (i = n - 1), arr[n - 1] gets set to -1, and running_max gets updated to the original value of the last element. From there, the running max grows monotonically as you move left.

Visual walkthrough

Notice how the running max only increases (or stays the same) as you move from right to left. That is because you are accumulating the maximum of a growing suffix. By the time you reach index 0, the running max holds the maximum of everything from index 1 onward, which is exactly the answer you need.

Complexity analysis

Time is O(n) because you visit each element exactly once. The loop runs n iterations, each doing O(1) work (one comparison and one assignment).

Space is O(1) because the modification happens in place. You only need a single variable (running_max) beyond the input array. No extra array or data structure is required.

The building blocks

1. Right-to-left traversal

Many array problems become simpler when you reverse the direction of traversal. If the answer at position i depends on elements to its right, scanning right to left lets you build up that information incrementally.

for i in range(n - 1, -1, -1):
    # process arr[i] with knowledge of everything to its right

This pattern appears in Daily Temperatures (processing from the right with a stack), Next Greater Element problems, and suffix-based computations like suffix sums and suffix maximums.

2. Running maximum

A running maximum tracks the largest value seen so far as you scan through an array. It is the maximum analog of a running sum.

running_max = initial_value
for value in sequence:
    running_max = max(running_max, value)

You will see this building block in Best Time to Buy and Sell Stock (running minimum for the buy price), Trapping Rain Water (prefix and suffix maximums), and any problem where you need "the largest element in some range" without recomputing from scratch each time.

Edge cases

• Single element array: [5] becomes [-1]. The only element has nothing to its right.
• All elements the same: [3, 3, 3, 3] becomes [3, 3, 3, -1]. The running max equals the common value at every position except the last.
• Sorted ascending: [1, 2, 3, 4] becomes [4, 4, 4, -1]. The maximum to the right of every position is always the last element.
• Sorted descending: [4, 3, 2, 1] becomes [3, 2, 1, -1]. Each element's replacement is the next element, since the array is decreasing.
• Two elements: [5, 10] becomes [10, -1]. The minimum case with meaningful replacement.

From understanding to recall

You have seen how a single right-to-left pass with a running maximum solves this problem in O(n) time and O(1) space. The logic fits in five lines of code. But the details matter: initializing running_max to -1, saving the new max before overwriting, updating after the assignment. These are the small things that slip away if you only read the solution once.

Spaced repetition is how you lock them in. You practice writing the right-to-left loop and running maximum from memory at increasing intervals. After a few rounds, the pattern is automatic. When you see a problem that asks about suffix maximums or right-side information, you reach for this building block without hesitation.

Related posts

• Product of Array Except Self - Another problem solved by scanning from both directions
• Daily Temperatures - Right-to-left processing with a stack to find next greater elements
• Rotate Array - Array manipulation requiring careful index handling

CodeBricks breaks Replace Elements into its right-to-left traversal and running maximum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an array problem shows up in your interview, you do not think about which direction to scan. You just know.