## DEV Community is a community of 755,328 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Leetcode 1299: Replace Elements with Greatest Element on Right Side

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

## Problem Statement

Given an array `arr`, 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.

Example 1:

``````Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
``````

Constraints:

• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^5

## Solution 1: two loops

``````var replaceElements = function(arr) {
let newArr = []
for(let i=0; i<arr.length; i++){
let max = arr[i+1]
for(let j=i+1;j<arr.length;j++){
let value = arr[j+1]
max = value > max? value: max
}
newArr.push(max)
}
newArr[arr.length-1] = -1
return newArr
};
``````

Time complexity : O(n²)
Space complexity : O(n)

## Solution 2: One loop

With last index as -1, we can start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element.

For example:

let arr = [17,18,5,4,6,1]

and as we know:

1. newArr is -1
2. newArr is equal to arr
3. newArr is equal to the maximum number among arr to arr. This is also equal to the maximum number among arr to newArr

To simplify the logic, we can describe like this:

``````newArr = max(arr[1:5]) = max(arr, newArr)
newArr = max(arr[2:5]) = max(arr, newArr)
newArr = max(arr[3:5]) = max(arr, newArr)
newArr = max(arr[4:5]) = max(arr, newArr)
newArr = arr
newArr = -1
``````

And the solution will be:

``````var replaceElements = function(arr) {
let newArr = [];
newArr[arr.length-1] = -1;
for (i = arr.length-2; i >= 0; i--) {
newArr[i] = Math.max(newArr[i+1],arr[i+1]);
}
return newArr;
};
``````

Time complexity : O(n)
Space complexity : O(n)