Replace Elements with Greatest Element on Right Side

Replace Elements with Greatest Element on Right Side

What is this problem about?

The Replace Elements with Greatest Element on Right Side interview question asks you to replace every element in an array with the greatest element among all elements to its right, and set the last element to -1. The result is a new array where each position holds the maximum value that appeared anywhere to its right in the original array.

Why is this asked in interviews?

This problem is asked at Meta, Zoho, Amazon, and Google as an introductory array traversal question. It tests whether candidates know to iterate from right to left while maintaining a running maximum — rather than using nested loops to recompute the max for each position. The right-to-left running max pattern appears in many harder problems, making this a valuable conceptual warm-up.

Algorithmic pattern used

The pattern is right-to-left linear scan with a running maximum. Initialize max_right = -1 (the sentinel for the last element). Traverse from right to left. For each index i, store max_right as the replacement value, then update max_right = max(max_right, original_nums[i]). This gives O(n) time and O(1) space if done in-place.

Example explanation

Array: [17, 5, 12, 8, 3, 22, 10]

Traverse right to left, tracking max_right:

• i=6 (10): result=-1, max_right=10.
• i=5 (22): result=10, max_right=22.
• i=4 (3): result=22, max_right=22.
• i=3 (8): result=22, max_right=22.
• i=2 (12): result=22, max_right=22.
• i=1 (5): result=22, max_right=22.
• i=0 (17): result=22, max_right=22.

Result: [22, 22, 22, 22, 22, 10, -1].

Common mistakes candidates make

• Iterating left to right and finding the max to the right for each position — O(n^2).
• Forgetting to set the last element to -1.
• Updating max_right before storing the result instead of after, producing incorrect values.
• Creating a separate array when in-place modification is allowed.

Interview preparation tip

For the Replace Elements with Greatest Element on Right Side coding problem, the array interview pattern is right-to-left scanning with a running max. This exact technique recurs in "next greater element," "trapping rainwater," and "stock span" problems. Interviewers at Meta and Google appreciate when you immediately name the pattern — it signals you recognize a reusable algorithmic idiom rather than solving each problem from scratch.