Replace Elements with Greatest Element on Right Side

Replace Elements with Greatest Element on Right Side - Problem

Array Easy

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.

Note: The rightmost element should always be replaced with -1 since there are no elements to its right.

Input & Output

Example 1 — Basic Case

$ Input: arr = [17,18,5,4,6,1]

› Output: [18,6,6,6,1,-1]

💡 Note: Element 17 → max(18,5,4,6,1) = 18, element 18 → max(5,4,6,1) = 6, element 5 → max(4,6,1) = 6, element 4 → max(6,1) = 6, element 6 → max(1) = 1, last element 1 → -1

Example 2 — Ascending Order

$ Input: arr = [1,2,3,4,5]

› Output: [5,5,5,5,-1]

💡 Note: For elements 1,2,3,4: the greatest element to the right is always 5. The last element 5 becomes -1

Example 3 — Single Element

$ Input: arr = [1]

› Output: [-1]

💡 Note: Only one element, so it becomes -1 as there are no elements to its right

Constraints

1 ≤ arr.length ≤ 10⁴
1 ≤ arr[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with elements to be replaced

Find Greatest Right

For each element, find maximum among elements to its right

Final Result

Array with replacements, last element is -1

Key Takeaway

🎯 Key Insight: Process the array from right to left to efficiently track the maximum element seen so far, eliminating the need to rescan elements multiple times.

Asked in

a Amazon 15 Ad Adobe 8

The key insight is to traverse from right to left, keeping track of the maximum element seen so far. This avoids recalculating the same maximum values multiple times. Best approach is the single-pass right-to-left traversal with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Right for Each Element	O(n²)	O(1)	For each element, scan all elements to its right to find the maximum
Optimized - Single Right-to-Left Pass	O(n)	O(1)	Traverse from right to left, keeping track of the maximum seen so far

Brute Force - Check Right for Each Element — Algorithm Steps

Step 1: For each element at index i (except last)
Step 2: Scan from i+1 to end to find maximum
Step 3: Replace arr[i] with that maximum
Step 4: Set last element to -1

Visualization

Tap to expand

Step-by-Step Walkthrough

For Each Position

Look at current element

Scan Right

Find maximum among all elements to the right

Replace

Set current element to that maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* arr, int arrSize, int* returnSize) {
    *returnSize = arrSize;
    // For each element except the last
    for (int i = 0; i < arrSize - 1; i++) {
        int maxRight = arr[i + 1];
        // Find maximum in remaining elements
        for (int j = i + 2; j < arrSize; j++) {
            if (arr[j] > maxRight) {
                maxRight = arr[j];
            }
        }
        arr[i] = maxRight;
    }
    
    // Last element becomes -1
    arr[arrSize - 1] = -1;
    return arr;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            arr[size++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(arr, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop runs n times, inner loop averages n/2 scans

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

99.6K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Right for Each Element — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler