1299. Replace Elements with Greatest Element on Right Side

• python3
• review : 20240709

📎 Problem

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]
Explanation: 
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Constraints:

• 1 <= arr.length <= 104
• 1 <= arr[i] <= 105

Pseudocode

1. check constarints
2. set two pointers and move
3. it will get n^2...

so I have to find another solution

1. Start from the end of the array.
2. Compare the max value with the current array element:If the max value is smaller than the current element, update the max value to the current element.
3. Replace the current element with the max value.
4. Return the array.

Code

first solution

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        
        # 0. check constraints
        if len(arr) == 1:
            return [-1]

        result = []

        for i in range(0, len(arr)):
            most = -1
            if i < len(arr) - 1:
                for j in range(i+1, len(arr)):
                 if most < arr[j]:
                    most = arr[j]
            else:
                result.append(-1)
                break
            result.append(most)

        return result

final solution

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

Result

• Time Complexity : O(n) as we are traveling the array only once.
• Space Complexity : O(1) as we are not using any extra space.

Review

• Always keep time complexity in mind.