algoadvance

You are given an array arr. For each index i in the array, you need to replace the element arr[i] with the greatest element among the elements to its right, and replace the last element with -1.

For example:

• Input: [17,18,5,4,6,1]
• Output: [18,6,6,6,1,-1]

Clarifying Questions

1. What are the constraints on the input array?
   • The number of elements (n) in arr is between 1 and 10^4.
   • Each element in the array is between 1 and 10^5.
2. What should be returned if the array is empty?
   • The problem guarantees that the array will contain at least one element.
3. Are there any specific requirements on time or space complexity?
   • It would be optimal to achieve O(n) time complexity.

Strategy

1. Iterate from Right to Left:
   • We start from the second last element and move towards the first element. This is because the current element needs to be replaced with the maximum element on its right side.
2. Track the Maximum Element:
   • Keep track of the maximum element found so far as we iterate from the right to the left.
3. Update Elements:
   • For each element, before updating it, store the current maximum so far in a variable, update this current element with the stored value, and then update the maximum so far.
4. Last Element:
   • The last element is always replaced with -1.

Code

def replaceElements(arr):
    n = len(arr)
    if n == 0:
        return arr

    # Initialize max_so_far with -1 since the last element should be replaced by -1
    max_so_far = -1
    
    # Iterate from the end to the beginning
    for i in range(n - 1, -1, -1):
        # Store the current element before we overwrite it
        current = arr[i]
        # Replace the current element with max_so_far
        arr[i] = max_so_far
        # Update max_so_far if current element is higher than max_so_far
        if current > max_so_far:
            max_so_far = current
        
    return arr

# Example usage
print(replaceElements([17,18,5,4,6,1]))  # Output: [18,6,6,6,1,-1]

Time Complexity

• Time Complexity: The solution involves a single pass through the array, leading to a time complexity of O(n), where n is the length of the array.
• Space Complexity: The space complexity is O(1) because we are using only a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?