Domain 1EasyCORE

Replace Elements with Greatest Element on Right Side

The problem requires us to replace each element in an array with the greatest element to its right. If there are no elements to the right of a given element (i.e., it's the last element), we should replace it with `-1`. The input is a single array of integers, and the output should be the modified array.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1299. Replace Elements with Greatest Element on Right Side

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 74.6%


Problem Breakdown

The problem requires us to replace each element in an array with the greatest element to its right. If there are no elements to the right of a given element (i.e., it’s the last element), we should replace it with -1. The input is a single array of integers, and the output should be the modified array.

Inputs:

  • arr: A list of integers where 1 <= arr.length <= 10^4 and 1 <= arr[i] <= 10^5.

Outputs:

  • A modified version of the input array where each element is replaced by the greatest element to its right, with the last element being -1.

Implicit Constraints or Tricky Edge Cases:

  • The array could have only one element.
  • All elements in the array are positive integers.

Intuition

A brute-force approach would involve iterating through each element of the array and for each element, finding the maximum value among all elements to its right. This approach would result in a time complexity of O(n^2), which is inefficient given the constraints.

The key insight to improve this solution is to start from the end of the array and move towards the beginning. By keeping track of the maximum value encountered so far, we can update each element in constant time as we iterate through the array. This approach reduces the time complexity to O(n).

Approach

  1. Initialize a variable max_right to -1, which will keep track of the maximum value encountered so far while iterating from right to left.
  2. Iterate through the array from the second last element to the first element (since the last element is replaced with -1).
  3. For each element, store its current value in a temporary variable temp.
  4. Replace the current element with max_right.
  5. Update max_right to be the maximum of max_right and temp.
  6. After the loop, replace the last element with -1.

Complexity Analysis

  • Time Complexity: O(n) because we iterate through the array once.
  • Space Complexity: O(1) as we are modifying the array in place and using only a constant amount of extra space.

Solution

def replaceElements(arr):
    max_right = -1
    for i in range(len(arr) - 2, -1, -1):
        temp = arr[i]
        arr[i] = max_right
        max_right = max(max_right, temp)
    arr[-1] = -1
    return arr

Edge Cases Handled

  • Single Element Array: The code correctly handles arrays with a single element by replacing it with -1.
  • All Elements Identical: If all elements are identical, the code will replace each element with itself except for the last one, which is replaced with -1.