Problem Description

You are given an array arr. Your task is to transform this array by replacing each element with the greatest element that appears to its right in the array. The last element should be replaced with -1 since there are no elements to its right.

For example, if you have an array [17, 18, 5, 4, 6, 1]:

• Element at index 0 (17) is replaced by the maximum of all elements to its right: max(18, 5, 4, 6, 1) = 18
• Element at index 1 (18) is replaced by the maximum of all elements to its right: max(5, 4, 6, 1) = 6
• Element at index 2 (5) is replaced by the maximum of all elements to its right: max(4, 6, 1) = 6
• Element at index 3 (4) is replaced by the maximum of all elements to its right: max(6, 1) = 6
• Element at index 4 (6) is replaced by the maximum of all elements to its right: max(1) = 1
• Element at index 5 (1) is the last element, so it's replaced by -1

The resulting array would be [18, 6, 6, 6, 1, -1].

The solution uses a reverse traversal approach. By iterating from right to left, we can keep track of the maximum value seen so far. At each position, we store the current maximum in that position and update our maximum tracker with the original value at that position. This way, each element gets replaced with the greatest element to its right efficiently in a single pass through the array.

Intuition

The key insight is that if we traverse the array from left to right, we would need to repeatedly scan the remaining elements to find the maximum for each position, which would be inefficient. However, if we traverse from right to left, we can maintain the maximum value seen so far and use it directly.

Think about it this way: when we're at the rightmost element, we know it should be replaced with -1. As we move left, each element needs the maximum of all elements to its right. But we've just visited those elements! So we can keep track of the running maximum as we go.

The clever part is realizing that at each position during our reverse traversal:

1. We already know what the maximum value to the right is (stored in our mx variable)
2. Before overwriting the current element, we need to save it to potentially update our maximum
3. After replacing the current element with mx, we update mx to be max(mx, original_value) for the next iteration

This way, we build our answer in a single pass. Starting from the right with mx = -1 ensures the last element gets -1 as required. As we move left, mx always contains the maximum of all elements we've seen so far (which are all the elements to the right of our current position).

The beauty of this approach is that we're essentially "carrying" the information we need (the maximum value) as we traverse, rather than recalculating it each time. This transforms what could be an O(n²) problem into an O(n) solution.

Solution Approach

The implementation uses a single-pass reverse traversal with a tracking variable to efficiently solve the problem.

Algorithm Steps:

1. Initialize the maximum tracker: Start with mx = -1. This serves as the initial value for the rightmost element (which has no elements to its right).

2. Reverse traversal: Use reversed(range(len(arr))) to iterate through array indices from right to left. This allows us to process each element while having already seen all elements to its right.

3. For each position i:

   • Store the original value: Save arr[i] in a temporary variable x before overwriting it
   • Replace with maximum: Set arr[i] = mx (the maximum of all elements to the right)
   • Update the maximum: Calculate mx = max(mx, x) to include the current element for future iterations

4. Return the modified array: The array is modified in-place and returned.

Example walkthrough with [17, 18, 5, 4, 6, 1]:

• Start: mx = -1
• Index 5 (value 1): x = 1, arr[5] = -1, mx = max(-1, 1) = 1
• Index 4 (value 6): x = 6, arr[4] = 1, mx = max(1, 6) = 6
• Index 3 (value 4): x = 4, arr[3] = 6, mx = max(6, 4) = 6
• Index 2 (value 5): x = 5, arr[2] = 6, mx = max(6, 5) = 6
• Index 1 (value 18): x = 18, arr[1] = 6, mx = max(6, 18) = 18
• Index 0 (value 17): x = 17, arr[0] = 18, mx = max(18, 17) = 18
• Result: [18, 6, 6, 6, 1, -1]

The time complexity is O(n) as we visit each element exactly once, and the space complexity is O(1) since we only use a constant amount of extra space for the tracking variable.

Example Walkthrough

Let's walk through the solution with a small example: arr = [5, 2, 3, 1]

Initial Setup:

• Start with mx = -1 (this will be the value for the last element)
• We'll traverse from right to left

Step-by-step execution:

Index 3 (value = 1):

• Save original: x = 1
• Replace with max to the right: arr[3] = mx = -1
• Update max for next iteration: mx = max(-1, 1) = 1
• Array now: [5, 2, 3, -1]

Index 2 (value = 3):

• Save original: x = 3
• Replace with max to the right: arr[2] = mx = 1
• Update max for next iteration: mx = max(1, 3) = 3
• Array now: [5, 2, 1, -1]

Index 1 (value = 2):

• Save original: x = 2
• Replace with max to the right: arr[1] = mx = 3
• Update max for next iteration: mx = max(3, 2) = 3
• Array now: [5, 3, 1, -1]

Index 0 (value = 5):

• Save original: x = 5
• Replace with max to the right: arr[0] = mx = 3
• Update max for next iteration: mx = max(3, 5) = 5
• Array now: [3, 3, 1, -1]

Final Result: [3, 3, 1, -1]

Each element has been replaced with the greatest element to its right:

• 5 → 3 (max of 2, 3, 1)
• 2 → 3 (max of 3, 1)
• 3 → 1 (max of 1)
• 1 → -1 (no elements to the right)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm iterates through the array exactly once in reverse order using reversed(range(len(arr))), performing constant-time operations (assignment, comparison with max()) at each step.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space - two variables mx and x - regardless of the input size. The modifications are done in-place on the original array, and the reversed() function returns an iterator that doesn't create a new list, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Store the Original Value Before Overwriting

One of the most common mistakes is directly updating arr[i] without first storing its original value. This leads to losing the element's value before it can be used to update the maximum tracker.

Incorrect Implementation:

def replaceElements(self, arr: List[int]) -> List[int]:
    max_so_far = -1
    for i in reversed(range(len(arr))):
        arr[i] = max_so_far  # Original value is lost!
        max_so_far = max(max_so_far, arr[i])  # Now using the replaced value (wrong!)
    return arr

Why it fails: After setting arr[i] = max_so_far, the original value at position i is lost. When updating max_so_far, we're using the already-replaced value instead of the original element, which breaks the algorithm.

Correct Solution:

def replaceElements(self, arr: List[int]) -> List[int]:
    max_so_far = -1
    for i in reversed(range(len(arr))):
        current_element = arr[i]  # Store original value first
        arr[i] = max_so_far
        max_so_far = max(max_so_far, current_element)  # Use the stored original value
    return arr

2. Traversing in the Wrong Direction (Left to Right)

Another pitfall is attempting to solve this problem by traversing from left to right, which seems intuitive but makes the solution unnecessarily complex.

Why left-to-right doesn't work efficiently: When at position i, you need to know the maximum of all elements from i+1 to the end. With left-to-right traversal, you'd need to either:

• Scan ahead for each element (O(n²) time complexity)
• Use additional data structures to precompute maximums

Right-to-left is optimal because: When processing element at index i, you've already processed all elements to its right and know their maximum, making it a single O(n) pass solution.

3. Incorrect Initial Value for Maximum Tracker

Setting the wrong initial value for max_so_far can cause incorrect results, especially for the last element.

Incorrect:

max_so_far = 0  # Wrong initial value

Why it fails: If all elements in the array are negative, using 0 as the initial value would incorrectly report 0 as the maximum to the right of some elements.

Correct: Always initialize with -1 as specified in the problem, since the last element should always be replaced with -1.