Given an array nums, 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.
Input: arr = [17, 18, 5, 4, 6, 1]
Output: [18, 6, 6, 6, 1, -1]
Explanation:
For index 0 - largest element to right side from idex 0 is 18.
For index 1 - largest element to right side from idex 1 is 6.
For index 2 - largest element to right side from idex 2 is 6.
For index 3 - largest element to right side from idex 3 is 6.
For index 4 - largest element to right side from idex 4 is 1.
For index 5 - last element should be replaced with -1.
Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.
Contents
- Solution 1 - using brute force approach
- Solution 2 - start copying largest elements from right side
In this approach, for every number at index i, we will check all remaining numbers to the right of the array
starting from i to n and get maximum number, then place that at index i.
Finally when we are at end index of array just put -1 as per problem statement.
public class ReplaceElementsWithGreatestFromRight {
/* brute force approach */
static int[] usingBruteForce(int[] nums) {
int[] ans = new int[nums.length];
for(int i=0; i<nums.length-1; i++) {
int greatest = 0;
for(int j=i+1; j<nums.length; j++) {
if(nums[j]>greatest) {
greatest = nums[j];
}
}
nums[i] = greatest;
}
nums[nums.length -1] = -1;
return nums;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n2) time where n is the length of
nums array, this is because we are looping through nums array in a nested for loop.
Space complexity: O(n) for the ans array or O(1) if you are allowed to modify input array and then return that as answer.
In this approach, we are going to start from the right end of nums array, first put -1 at the end. Thereafter, compare the maximum between
the elements from ans array at i+1 index and nums array at i+1 index.
ans[i] = MAX(ans[i+1], nums[i+1]);
The reason we do this is because:
-
When we are at index i+1 in nums array ans array holds maximum value up until i+2 index.
-
When we are at index i in nums array ans array holds maximum value up until i+1 index.
So, ans always holds maximum up until one index after current index and when move index to the left side,
we need look into maximum element so far from ans array, then next element from nums array.
Let's look at below diagram for input nums= {17, 18, 5, 4, 6, 1}
public class ReplaceElementsWithGreatestFromRight {
/* we start copying largest from right side*/
static int[] copyLargestFromRightSide(int[] nums) {
int[] ans = new int[nums.length];
ans[nums.length -1] = -1;
for(int i=nums.length-2; i>=0; i--) {
ans[i] = Math.max(nums[i+1], ans[i+1]);
}
return ans;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the length of nums
array since we are looping through input array only once.
Space complexity: O(n) for the ans array.
Above implementations source code can be found at
GitHub link for Java code