Solution Explanation: Replace Elements with Greatest Element on Right Side

This problem requires replacing each element in an array with the greatest element to its right. The last element is replaced with -1. The optimal solution involves a single pass through the array from right to left.

Approach:

The core idea is to maintain a variable that tracks the maximum value encountered so far while iterating from right to left.

1. Initialization: Start with a variable mx initialized to -1. This represents the maximum element encountered so far (initially, no elements have been seen from the right).

2. Iteration: Iterate through the array from the rightmost element to the leftmost element.

3. Update: For each element arr[i]:

   • Replace arr[i] with the current maximum value mx.
   • Update mx to be the maximum of mx and arr[i] (the original value of the element before replacement). This ensures mx always holds the largest element encountered to the right of the current position.

4. Return: After iterating through the entire array, return the modified array.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the array. We iterate through the array once.
• Space Complexity: O(1). We use a constant amount of extra space to store the mx variable.

Code Implementation (Python):

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

Code Implementation (Java):

class Solution {
    public int[] replaceElements(int[] arr) {
        int mx = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            int x = arr[i];
            arr[i] = mx;
            mx = Math.max(mx, x);
        }
        return arr;
    }
}

Code Implementation (C++):

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int mx = -1;
        for (int i = arr.size() - 1; i >= 0; --i) {
            int x = arr[i];
            arr[i] = mx;
            mx = max(mx, x);
        }
        return arr;
    }
};

Code Implementation (Go):

func replaceElements(arr []int) []int {
	mx := -1
	for i := len(arr) - 1; i >= 0; i-- {
		x := arr[i]
		arr[i] = mx
		mx = max(mx, x)
	}
	return arr
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Code Implementation (TypeScript):

function replaceElements(arr: number[]): number[] {
    let mx = -1;
    for (let i = arr.length - 1; i >= 0; i--) {
        let x = arr[i];
        arr[i] = mx;
        mx = Math.max(mx, x);
    }
    return arr;
}

All these code snippets implement the same algorithm and achieve the same time and space complexity. They differ only in syntax specific to their respective programming languages.