1299. Replace Elements with Greatest Element on Right Side

# Question

Given an array arr, replace every element in that array with the greatest element strictly to its right, and replace the last element with -1. Return the modified array in-place.

# Solution

# Pattern

Reverse Traversal (Right-to-Left) When a problem requires aggregating information from elements to the right of the current index, iterate from right to left. This carries the "future" state backward, allowing you to compute answers in $O(1)$ time per element.

# How to Identify

• The problem requires making decisions based on the "remaining" array (everything to the right).
• A brute force approach naturally leans toward nested loops $O(N^2)$.
• The information needed from the right side is an aggregate metric (e.g., maximum, minimum, sum, product).

# Description

Step-by-step explanation:

1. Validate the input to ensure the array is not null or empty.
2. Initialize a state variable, maxRight, to -1. This mathematically satisfies the requirement for the last element and seeds our maximum tracker.
3. Iterate backward through the array, starting from arr.length - 1 down to 0.
4. At each step, store the actual value of arr[i] into a temporary variable currentVal. We need this because we are about to overwrite arr[i], but we still need its original value to calculate the max for the elements to its left.
5. Overwrite arr[i] with maxRight.
6. Update maxRight by taking the maximum of its current value and currentVal.
7. Continue until the loop terminates, then return the in-place modified array.

# The Intuition

Think of this algorithm as walking backward through time. If you walk forward (left-to-right), you don't know what the biggest number ahead of you is unless you run ahead to check (costing $O(N)$ time per step). But if you start at the end and walk backward, you can just carry the biggest number you've found so far in your pocket. When you step onto a new number, you simply take the big number out of your pocket, write it down, and then check if the number you just stepped on is bigger than the one in your pocket. If it is, you swap it. This gives you perfect "hindsight" in a single pass.

# Complexity

# Time Complexity

We traverse the array of size $N$ exactly once. Inside the loop, we perform $O(1)$ constant-time operations (variable assignments and a Math.max comparison). Total time complexity is strictly $O(N)$.

# Space Complexity

We modify the input array in-place. We allocate exactly two integer primitives (maxRight and currentVal) regardless of how large the input array is. Therefore, auxiliary space is strictly $O(1)$.

# Code

class Solution {
    public int[] replaceElements(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr; 
        }
 
        int maxRight = -1;
        
        for (int i = arr.length - 1; i >= 0; i--) {
            // Cache the current element before overwriting
            int currentVal = arr[i];
            
            // Replace with the greatest element seen so far from the right
            arr[i] = maxRight;
            
            // Update the max for the next iteration (moving left)
            maxRight = Math.max(maxRight, currentVal);
        }
 
        return arr;
    }
}

# Caveats

• Immutability Constraints: In some strict functional programming environments or multi-threaded contexts, mutating the input array (arr[i] = ...) is an anti-pattern or expressly forbidden. In such cases, you must sacrifice $O(1)$ space and allocate a new result array of size $N$.
• Stream Processing: If the array is arriving as an unbounded stream (e.g., live stock prices) where you must output the answer for day $i$ immediately before seeing day $i+1$, this reverse-traversal approach is physically impossible.

# Concepts to Think About

• State Propagation: Notice how the state (maxRight) strictly propagates in one direction. This is a foundational building block for 1D Dynamic Programming.
• In-Place Swapping Mechanics: The temp variable pattern used here is universal. Whenever you need to read and write to the same memory location where the old value influences future writes, a temporary cache is required.
• Cache Locality: Reverse iteration has the exact same highly efficient cache locality as forward iteration. The CPU prefetches the contiguous memory blocks backward just as effectively.

# Logical Follow-up

Question: Find all the "Leaders" in an array. An element is a leader if it is strictly greater than all the elements to its right side. Solution: We use the exact same reverse-traversal pattern. Initialize maxRight = -infinity. Iterate from right to left. If arr[i] > maxRight, it is a leader; add it to the result list, and update maxRight = arr[i]. This solves the problem in $O(N)$ time and $O(1)$ space (excluding the output list).

Question: What if you needed to replace every element with the next strictly greater element to its right (not the absolute maximum), and -1 if none exists? (Next Greater Element) Solution: A single state variable no longer works because the "next greater" isn't necessarily the global maximum. We must use a Monotonic Stack. Iterate right-to-left. While the stack is not empty and the top of the stack is $\le arr[i]$, pop it. If the stack becomes empty, the answer is -1. Otherwise, the answer is the top of the stack. Push $arr[i]$ to the stack. This requires $O(N)$ time and $O(N)$ space.