easy

Replace Elements with Greatest Element on Right Side

Replace each value with the greatest value to its right.

1. Define the problem

Replace Elements with Greatest Element on Right Side

Given an array arr, replace every element with the greatest element among the elements to its right, and replace the last element with -1. Walk the array from right to left , keeping a running maximum of everything already visited, so every position can be overwritten using only values further right.

Constraints

  • 1 ≤ arr.length ≤ 104
  • 1 ≤ arri ≤ 105

Example

Inputarr = [17, 18, 5, 4, 6, 1]
Output[18, 18, 6, 6, 1, -1]

Explanation The greatest element to the right of index 0 is 18, of index 1 is 6, and so on; the last element becomes -1.

2. Visualize the solution

Scan from the right, tracking the max seen so far

Scan from the right, tracking the max seen so far
Statusinit

i=5 (value 1). runningMax=-1. Set arr[5]=-1, then runningMax becomes max(-1, 1)=1.

What happens in this step

i = 5, arr[5] = 1, runningMax = -1
arr[5] = runningMax = -1
runningMax = max(-1, 1) = 1
Step 1 of 4

Steps to visualize

  1. Start a runningMax at -1 and walk the array from the last index to the first.
  2. At each index, save the current value before overwriting it.
  3. Set arri to runningMax.
  4. Update runningMax to be the larger of runningMax and the saved value.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Scan from the right, tracking the max seen so far
Statusinit

i=5 (value 1). runningMax=-1. Set arr[5]=-1, then runningMax becomes max(-1, 1)=1.

What happens in this step

i = 5, arr[5] = 1, runningMax = -1
arr[5] = runningMax = -1
runningMax = max(-1, 1) = 1
Step 1 of 4
4. Solution

Solution

solution.tsTypeScript
function replaceElements(arr) {
  const result = arr.slice();
  let runningMax = -1;

  for (let i = result.length - 1; i >= 0; i--) {
    const current = result[i];
    result[i] = runningMax;
    runningMax = Math.max(runningMax, current);
  }

  return result;
}
Time
O(n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
arr = [17, 18, 5, 4, 6, 1][18, 6, 6, 6, 1, -1]example from the docstring
arr = [400][-1]smallest valid input, a single element becomes -1
arr = [1, 2][2, -1]boundary case, exactly two elements
arr = [5, 4, 3, 2, 1][4, 3, 2, 1, -1]strictly decreasing array, each element is its own right neighbor max
arr = [3, 3, 3][3, 3, -1]every value identical except the trailing -1
arr = [1, 2, 3, 4][4, 4, 4, -1]strictly increasing array, max always comes from the far right

Keep reading