[Arrays] Replace Elements with Greatest Element on Right Side

📋 This is my note-taking from what I learned in LeetCode!

Problem

Problem Link

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]
• 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:

• Input: arr = [400]
• Output: [-1]
• Explanation: There are no elements to the right of index 0.

Constraints:

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

Hint #1:

Loop through the array starting from the end.

Hint #2:

Keep the maximum value seen so far.

Solution

Approach 1

Algorithm:

1. Initialize a variable max_value to -1.

2. Loop through the array from the end to the beginning:

   • Set the current element to temp(temporary variable).

   • Replace the current element with max_value.

   • Update max_value as max(max_value, temp).

3. Replace the last element with -1.
4. Return the modified array.

def replaceElements(arr: list[int]) -> list[int]:
    n = len(arr)
    max_val = -1
    for i in range(n - 1, -1, -1):
        temp = arr[i]
        arr[i] = max_val
        max_val = max(max_val, temp)
    return arr

arr = [17, 18, 5, 4, 6, 1]
result = replaceElements(arr)
print(result)  # Output: [18, 6, 6, 6, 1, -1]

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array arr.
• Space Complexity: O(1).

For Better Understanding

for i in range(n-1, -1, -1)

The line for i in range(n-1, -1, -1) creates a loop that iterates over the range of integers from n-1 down to 0, in reverse order with a step of -1 (decrementing by 1).

In other words, it starts the loop with i equal to n-1, then executes the loop body, then decrements i by 1 and repeats the process until i is equal to -1, which is the stopping condition.

This type of loop is commonly used to iterate over the elements of an array or list in reverse order, from the last element to the first.

---

Back to Top

See other articles in Category Arrays