Problem Statement

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. URL

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

Approach 1

  • Naive implementation with Brute force approach.

#collapse-hide
from typing import List

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

sol = Solution()
sol.replaceElements([17,18,5,4,6,1])

[18, 6, 6, 6, 1, -1]
testCastList[:10]

[17646, 57573, 27167, 39539, 65701, 87804, 79104, 49477, 25757, 61518]
len(testCastList)

10000

Worst case performance in Time: $O(n^{2})$

Approach 2 

#collapse-hide
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        arrLen = len(arr)
        maxSoFar = arr[arrLen-1]
        arr[arrLen-1] = -1 
        
        for i in range(arrLen-2, -1, -1):
            temp = arr[i]
            arr[i] = maxSoFar
            if temp > maxSoFar:
                maxSoFar = temp 
        
        return arr

sol = Solution()
sol.replaceElements([17,18,5,4,6,1])

[18, 6, 6, 6, 1, -1]

Worst case performance in Time: $O(n)$