# Replace Elements with Greatest Element on Right Side
**Difficulty:** EASY
[External](https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side)
Canonical: https://scaleengineer.com/dsa/problems/replace-elements-with-greatest-element-on-right-side
**Data structures:** Array
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
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.

**Example 1:**

**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.

**Example 2:**

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

**Constraints:**

* `1 <= arr.length <= 104`
* `1 <= arr[i] <= 105`

# Approaches
## Brute Force with Nested Loops
This approach uses nested loops to solve the problem. The outer loop iterates through each element of the array that needs to be replaced. For each of these elements, an inner loop scans all subsequent elements to find the greatest one among them.
**Time:** O(n^2), where n is the length of the array. The outer loop runs n-1 times, and for each iteration, the inner loop can run up to n-1 times. This results in a quadratic number of comparisons. · **Space:** O(1). The replacement is done in-place, and only a few variables are used for loops and storing the maximum value, so the extra space is constant.
**Pros:** Straightforward to understand and implement as it directly follows the problem's definition.; It modifies the array in-place, requiring no extra space proportional to the input size.
**Cons:** Highly inefficient due to its O(n^2) time complexity.; For large inputs (as allowed by the constraints, up to 10^4), this approach will be too slow and likely result in a 'Time Limit Exceeded' error on coding platforms.
### Explanation
The brute-force method directly translates the problem statement into code. We iterate through the array from the first element up to the second-to-last element. For each element at index `i`, we perform a search on the subarray to its right (from `i+1` to the end) to find the maximum value. Once this maximum value is found, we replace the element at index `i` with it. This process is repeated for all elements. Finally, since the last element has no elements to its right, it is replaced with `-1` as per the problem's requirement. While simple to conceptualize, this method involves a lot of redundant calculations, as the search for the maximum is repeated for overlapping subarrays.

```java
class Solution {
    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return arr;
        }

        for (int i = 0; i < n - 1; i++) {
            int maxVal = arr[i + 1];
            for (int j = i + 2; j < n; j++) {
                if (arr[j] > maxVal) {
                    maxVal = arr[j];
                }
            }
            arr[i] = maxVal;
        }

        arr[n - 1] = -1;
        return arr;
    }
}
```
### Algorithm
1. Get the length of the array, `n`.
2. Iterate through the array with an outer loop from `i = 0` to `n - 2`.
3. For each element `arr[i]`, initialize a variable `max_val` to be the first element on its right, `arr[i+1]`.
4. Start an inner loop from `j = i + 2` to `n - 1`.
5. In the inner loop, update `max_val` by comparing it with `arr[j]`: `max_val = Math.max(max_val, arr[j])`.
6. After the inner loop finishes, the `max_val` holds the greatest element to the right of `arr[i]`. Replace `arr[i]` with `max_val`.
7. After the outer loop completes, all elements except the last one are updated. Set the last element `arr[n - 1]` to `-1`.
8. Return the modified array.

## Optimized Single Pass from Right to Left
A much more efficient solution involves a single pass through the array from right to left. By traversing in reverse, we can keep track of the maximum element seen so far. This maximum is precisely the value needed for the element to its immediate left.
**Time:** O(n), where n is the length of the array. We iterate through the array only once. · **Space:** O(1). The algorithm uses only a couple of variables (`maxFromRight`, `currentElement`) regardless of the input array size. The modification is done in-place.
**Pros:** Extremely efficient with a linear time complexity of O(n).; Optimal space complexity of O(1) as it modifies the array in-place.; It is the most performant solution for this problem.
**Cons:** The logic of iterating from right to left and updating the maximum value might be slightly less intuitive to grasp initially compared to the straightforward brute-force approach.
### Explanation
This optimal approach cleverly avoids redundant computations by iterating backward. We start from the rightmost element. The greatest element to its right is non-existent, so we know its replacement is `-1`. We can initialize a variable, `maxFromRight`, to `-1`. Then, we iterate from the last index `n-1` down to `0`. At each index `i`, the current `maxFromRight` is the answer for `arr[i]`. Before moving to the next element on the left (`i-1`), we update `maxFromRight` by comparing it with the original value of `arr[i]`. This way, as we move left, `maxFromRight` always holds the maximum of all elements we have visited so far (which are the elements to the right of the current position). This allows us to update the array in a single pass.

```java
class Solution {
    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int maxFromRight = -1;

        for (int i = n - 1; i >= 0; i--) {
            // Store the original value of the current element
            int currentElement = arr[i];
            
            // Replace the current element with the max found so far from the right
            arr[i] = maxFromRight;
            
            // Update the max from the right for the next element to the left
            maxFromRight = Math.max(maxFromRight, currentElement);
        }
        
        return arr;
    }
}
```
### Algorithm
1. Initialize a variable `maxFromRight` to `-1`. This variable will store the greatest element encountered so far as we traverse from the right.
2. Get the length of the array, `n`.
3. Iterate through the array in reverse order, from index `i = n - 1` down to `0`.
4. Inside the loop, for each element `arr[i]`, store its original value in a temporary variable, e.g., `currentElement = arr[i]`.
5. Replace the current element `arr[i]` with the current value of `maxFromRight`. At this point, `maxFromRight` holds the greatest element to the right of the *original* `arr[i]`.
6. Update `maxFromRight` to be the maximum of its current value and the `currentElement` we just processed: `maxFromRight = Math.max(maxFromRight, currentElement)`.
7. After the loop finishes, the array is correctly modified. Return `arr`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]: m = - 1 for i in range(len(arr) - 1, - 1, - 1): t = arr[i] arr[i] = m m = max(m, t) return arr

```