Replace Elements with Greatest Element on Right Side

Here’s a Python solution using a reverse iteration, which is more efficient and avoids creating an extra copy of the list:

1
2
3
4
5
6

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_val = -1
        for i in range(len(arr) - 1, -1, -1):
            arr[i], max_val = max_val, max(max_val, arr[i])
        return arr

This solution works from the end of the array towards the beginning. For each element, it replaces the current element with the current maximum (max_val) and then updates max_val to be the maximum of the current element and max_val.

Note that this solution modifies the original array arr in place, as allowed by the problem statement. This is generally more efficient than creating a new array, but should be done with care when the original array should not be modified.

Here’s a detailed explanation of the solution:

  • Initially, we set max_val as -1 because it’s the value we should assign to the last element according to the problem requirements.
  • Then, we start a loop that iterates over the array from the end to the beginning (from right to left).
  • For each element in the array, we do two things:
    1. Replace the current element with the greatest element seen so far (i.e., max_val).
    2. Update max_val by comparing it with the current element and taking the maximum of the two. We use the value of the current element before the replacement because we need to consider it for the computation of the greatest element among the elements to its right.
  • By the end of the loop, the array will have all the elements replaced with the greatest element to their right, and the last element replaced with -1, as required.

Imagine you are given a list of numbers. You are asked to replace each number in the list with the biggest number that appears after it in the list. If there’s no number after a particular number, you replace it with -1.

To do this, you would start from the end of the list and move towards the start. Why? Because for the last element, you already know that there’s no number after it, so you can replace it with -1.

For each other number, you keep track of the maximum number you’ve seen so far (let’s call it mx). When you are considering the next number in the list (moving towards the start), you know that mx is the biggest number that comes after it. So you can replace that number with mx.

However, before you replace the current number with mx, you should check if the current number is bigger than mx. If it is, you should update mx with the current number’s value. This ensures that mx always contains the biggest number seen so far.

You continue this process until you’ve considered all numbers in the list. At the end of this process, each number in the list has been replaced with the largest number that was originally to its right.

Q&A

I don’t get how we are getting o(N^2) runtime when sunning forward. Can anyone explain?

Running the algorithm forward instead of backward might tempt you to nest loops, resulting in a O(N^2) time complexity. Here’s why:

Let’s say you’re at position i in the array. If you run the algorithm forward, you would look at every element to the right of i to find the maximum. That would require scanning through N-i elements, where N is the total number of elements.

If you do this for each element, you’d have a nested loop:

  1. The outer loop runs N times.
  2. For each run of the outer loop, the inner loop runs N-i times.

When you add up the total number of operations, it gives you (N-1) + (N-2) + … + 1, which sums up to (N^2 - N)/2. As N gets larger, the N^2 term dominates, so we say the time complexity is O(N^2).

However, if you run the algorithm backward, you can keep track of the maximum element seen so far. This way, you only need to scan the array once, resulting in a O(N) time complexity.