We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace Elements with Greatest Element on Right Side

Number: 1231

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

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

Key Insights

  • The last element always becomes -1 since there are no elements to its right.
  • By iterating the array from right to left, you can maintain the maximum element seen so far.
  • This reverse traversal allows constant time updates and avoids the need for nested loops.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of elements in the array (single pass from right to left). Space Complexity: O(1) - in-place updates with only a few extra variables.

Solution

The strategy is to start from the end of the array and move leftwards. Track the maximum value observed so far (initialized as -1). For each element, replace it with the current maximum, then update the maximum if the current element is greater. This approach guarantees that each element is replaced by the greatest element to its right in a single traversal.

Code Solutions

# Define the function to replace elements
def replaceElements(arr):
    # Initialize max_value as -1 for the last element replacement
    max_value = -1
    # Traverse the array from the last index to the first index
    for i in range(len(arr) - 1, -1, -1):
        # Store the current element before replacement
        current_value = arr[i]
        # Replace the current element with the max_value
        arr[i] = max_value
        # Update max_value if the current element is greater
        if current_value > max_value:
            max_value = current_value
    return arr

# Example usage:
arr = [17, 18, 5, 4, 6, 1]
print(replaceElements(arr))  # Output: [18, 6, 6, 6, 1, -1]
← Back to All Questions