1299. Replace Elements with Greatest Element on Right Side

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

Solution 1

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:

        index = len(arr) - 2
        big = arr[-1]

        while index >= 0:
            temp = arr[index]
            arr[index] = big
            big = max(big, temp)

            index -= 1

        arr[-1] = -1

        return arr

This solution solves the problem by looping from the right size of the list and keeping track of the maximum value we’ve already seen. For each new element we arrive at, we replace it with the maxium value that we’ve seen before it.

Solution 1

Try it on Leetcode