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.

LeetCode

• https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/description/

Constraints

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

Examples

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.

Different Approaches

1️⃣ Brute Force Approach

🔍 Intuition:

For every element, find the maximum element on its right by scanning all elements after it.

🧠 Approach:

1. For each index i, iterate from i+1 to n-1 to find the maximum.
2. Replace arr[i] with the max found.
3. Set the last element to -1.

Code:

// Function to replace every element with the greatest element on its right side
vector<int> replaceElements(vector<int>& arr) {
    int n = arr.size();  // Step 1: Get the size of the input array

    // Step 2: Traverse each element from index 0 to n-2
    for (int i = 0; i < n - 1; ++i) {
        // Step 2.1: Assume the next element is the maximum initially
        int maxVal = arr[i + 1];

        // Step 2.2: Traverse the rest of the elements to the right of i
        for (int j = i + 2; j < n; ++j) {
            // Step 2.3: Update maxVal if a greater element is found
            maxVal = max(maxVal, arr[j]);
        }

        // Step 2.4: Replace current element with the maximum found to its right
        arr[i] = maxVal;
    }

    // Step 3: Set the last element to -1 since there are no elements to its right
    arr[n - 1] = -1;

    // Step 4: Return the modified array
    return arr;
}

Complexity Analysis:

• Time Complexity:O(n)
  • As we are iterating over the array once.
• Space Complexity: O(1)
  • No extra space is used.

2️⃣ Optimized Approach (Right to Left Traversal)

🔍 Intuition:

Instead of checking every element to the right for each index, keep track of the maximum so far from the right, and update elements from the end.

🧠 Approach:

1. Initialize maxRight = -1.
2. Traverse the array from right to left.
3. For each element:
   1. Store the current value in a temp variable.
   2. Replace the current element with maxRight.
   3. Update maxRight to be the maximum of temp and maxRight.

Code:

// Function to replace each element in the array with the greatest element to its right
// The last element is replaced with -1
vector<int> replaceElements(vector<int>& arr) {
    int maxRight = -1;  // Step 1: Initialize the maximum seen so far from the right as -1

    // Step 2: Traverse the array from right to left
    for (int i = arr.size() - 1; i >= 0; --i) {
        int current = arr[i];      // Step 3: Store the current value before overwriting

        arr[i] = maxRight;         // Step 4: Replace the current element with maxRight

        maxRight = max(maxRight, current); // Step 5: Update maxRight to be the max of itself and the original current value
    }

    // Step 6: Return the modified array
    return arr;
}

Complexity Analysis:

• Time Complexity:O(n)
  • We are traversing the array once.
• Space Complexity:O(1)
  • Only constant space is used.