Medium

# 455. Replace array elements with maximum element on the right.

Objective: Given an array of integers, write a program to replace its elements with the maximum element on the right side from their respective positions.

Note: If the element is equal to the maximum element on the right, replace it with 0.

Example:

```Original Array: [2, 5, 1, 6, 3, 4]
Output: [6, 6, 6, 0, 4, 0]
```

(For elements 2, 5, 1 the maximum element at the right side is 6, so replace these by 6, there is no element bigger than 6 at the right of 6 so replace 6 with 0 at its index. Similarly, for element 3, the maximum element at the right side is 4 so replace it by 4 and at the last index put 0)

```Original Array: [4, 5, 6, 7, 8]
Output: [8, 8, 8, 8, 0]

Original Array: [5, 4, 3, 2, 1]
Output: [0, 0, 0, 0, 0]
```

Approach

Brute Force: For each element, compare it with all the elements on the right and pick the maximum and replace the element with it.

Time Complexity: O(N2)

Better Solution:

• If array size is 0, return.
• Initialize max_so_far = array last element.
• Iterate the array from right to left.
• If the visited element is smaller than max_so_far, replace element by max_so_far
• If the visited element is equal to max_so_far, replace element by 0
• If the visited element is greater than max_so_far, do max_so_far = element and element = 0

Time Complexity: O(N)

Output:

```Original Array: [4, 5, 6, 7, 8]
Output: [8, 8, 8, 8, 0]

Original Array: [5, 4, 3, 2, 1]
Output: [0, 0, 0, 0, 0]
```