Programming

Programming problem: Replace Elements With Greatest Element On Right Side

Traverse the array right to left, tracking the running maximum. Each element gets replaced with the current max before updating it. This avoids the inner loop, reducing time complexity from O(n²) to O(n) with O(1) space.

Programming problem: Replace Elements With Greatest Element On Right Side

Question

You are 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 = [2,4,5,3,1,2]

Output: [5,5,3,2,2,-1]

Example 2

Input: arr = [3,3]

Output: [3,-1]

Constraints

  • 1 <= arr.length <= 10,000
  • 1 <= arr[i] <= 100,000

Solution

function replaceElements(arr: number[]): number[] {
  for (let i = 0; i < arr.length; i++) {
    let max: number = arr[i + 1];
    let maxIndex: number = i + 1;

    for (let k = i + 2; k < arr.length; k++) {
      if (arr[k] <= max) continue;
      maxIndex = k;
      max = arr[k];
    }

    arr[i] = maxIndex < arr.length ? max : -1;
  }

  return arr;
}

Read next