|
This post is completed by 3 users
|
Add to List |
518. Replace Elements with Greatest Element on Right
Given an array of numbers nums[], write ment a function to replace each element of the array with the greatest element present to its right side. Replace the last element with -1.
Example:
Input: [4, 5, 2, 25, 13, 16, 8] Output: [25, 25, 25, 16, 16, 8, -1] Input: [4, 5, 2, 25, 13, 16, 38] Output: [38, 38, 38, 38, 38, 38, -1]
Approach:
Naive solution would be to use the nested loops and compare each element of the array with all the elements of the array to it right and replace it with the maximum one and the last element with the -1 but the problem with the solution is that time complexity is high which is O(N^2).
Better Solution:
Initialize max = -1. Now iterate the array from right to left and replace the current element with the max element. Now check if max is < current element, if yes then replace the max with current element. Once the iteration is done, return the updated array.
Time Complexity: O(N)
Output:
Input: [4, 5, 2, 25, 13, 16, 8] Output: [25, 25, 25, 16, 16, 8, -1]
Reference: https://www.careercup.com/question?id=16835662