# 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)**

**Complete Code:**

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