Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input:
arr = [17,18,5,4,6,1]
Output:
 [18,6,6,6,1,-1]
Explanation:
- index 0 → the greatest element to the right of index 0 is index 1 (18).
- index 1 → the greatest element to the right of index 1 is index 4 (6).
- index 2 → the greatest element to the right of index 2 is index 4 (6).
- index 3 → the greatest element to the right of index 3 is index 4 (6).
- index 4 → the greatest element to the right of index 4 is index 5 (1).
- index 5 → there are no elements to the right of index 5, so we put -1.

Example 2:

1
2
3
4

Input:
arr = [400]
Output:
 [-1]

Solution

Method 1 - Starting From End of Array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	public int[] replaceElements(int[] arr) {
		int n = arr.length;
		int max = -1; // max from right
		for (int i = n - 1; i >= 0; i--) {
			int temp = arr[i];
			arr[i] = max;
			max = Math.max(max, temp);
		}
		return arr;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        max_from_right = -1  # Initialize max from the right

        # Traverse the array from right to left
        for i in range(n - 1, -1, -1):
            # Store the current value of arr[i] in a temporary variable
            temp = arr[i]
            # Replace arr[i] with the current max_from_right value
            arr[i] = max_from_right
            # Update max_from_right
            max_from_right = max(max_from_right, temp)

        return arr

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)