This post is completed by 1 user

  • 0
 Add to List
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]

Related Problems: