## 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.

Kira

Posted on

# 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[5] is -1
2. newArr[4] is equal to arr[5]
3. newArr[3] is equal to the maximum number among arr[4] to arr[5]. This is also equal to the maximum number among arr[4] to newArr[4]

To simplify the logic, we can describe like this:

``````newArr[0] = max(arr[1:5]) = max(arr[1], newArr[1])
newArr[1] = max(arr[2:5]) = max(arr[2], newArr[2])
newArr[2] = max(arr[3:5]) = max(arr[3], newArr[3])
newArr[3] = max(arr[4:5]) = max(arr[4], newArr[4])
newArr[4] = arr[5]
newArr[5] = -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)

## Discussion (2)

Tsuifei Pommier

Thanks Kira, explained very clearly :D

Azeez Abiodun Solomon

Thanks