Replace Elements with Greatest Element on Right Side

Difficulty: Easy | Acceptance: 72.20% | Paid: No Topics: Array

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.

• Examples
• Constraints
• Brute Force
• Reverse Iteration

Examples

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.

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

Constraints

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

Brute Force

Intuition For each element in the array, we can scan all the elements to its right to find the maximum value.

Steps

• Iterate through the array from the first element to the second to last element.
• For each element at index i, initialize a max_val to -1.
• Iterate through the subarray starting from i + 1 to the end of the array.
• Update max_val if a larger element is found.
• Replace the element at index i with max_val.
• Set the last element of the array to -1.

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

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays.

Reverse Iteration

Intuition If we traverse the array from right to left, we can keep track of the maximum element encountered so far. This allows us to update each element in a single pass.

Steps

• Initialize a variable max_so_far to -1.
• Iterate through the array from the last element down to the first.
• Store the current element in a temporary variable.
• Replace the current element with max_so_far.
• Update max_so_far to be the maximum of max_so_far and the temporary variable.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with linear time complexity.