Replace Elements with Greatest Element on Right Side

Replace every element with the largest element to its right. The last one becomes -1, because it has nothing to its right.

replaceElements([]int{17, 18, 5, 4, 6, 1})   // [18 6 6 6 1 -1]

The obvious way

For each position, scan everything after it:

for i := range arr {
    best := -1
    for j := i + 1; j < len(arr); j++ {
        best = max(best, arr[j])
    }
    result[i] = best
}

$O(n^2)$ , and it recomputes almost the same maximum $n$ times.

Walk the other way

The maximum to the right of position i is the maximum to the right of i+1, combined with arr[i+1]. That is a one-step relationship — so going right to left, each answer is available immediately.

Step 1 / 6

arr

17185461

result

·····-1

running max to the right = 1

The last element has nothing to its right, so its answer is −1 by definition. That is the base case, and it is why the walk goes right to left.

func replaceElements(arr []int) []int {
    var size = len(arr)
    var result = make([]int, size)

    for i := range arr {
        if i == 0 {
            result[size-1-i] = -1
        } else {
            result[size-1-i] = max(result[size-i], arr[size-i])
        }
    }

    return result
}

$O(n)$ time. The loop counts up while the indices count down — size-1-i walks backwards as i walks forwards.

The base case is the last element, not the first

result[size-1] = -1 is not an initialisation detail — it is what makes the recurrence terminate. Every other answer is defined in terms of the one after it, and this is the one that has no “after”.

Writing the loop forwards and the indices backwards makes that easy to lose track of. The clearer spelling is to let the loop run backwards too:

result := make([]int, len(arr))
running := -1

for i := len(arr) - 1; i >= 0; i-- {
    result[i] = running                 // answer first…
    running = max(running, arr[i])      // …then this element joins the max
}

Same algorithm, and the order of those two lines is the algorithm: swap them and every element includes itself.

Doing it without the extra array

The problem allows overwriting arr in place, which drops the space to $O(1)$ :

func replaceElements(arr []int) []int {
    running := -1
    for i := len(arr) - 1; i >= 0; i-- {
        arr[i], running = running, max(running, arr[i])
    }
    return arr
}

Go’s multiple assignment evaluates the whole right-hand side before assigning, so arr[i] on the right is still the old value when running is computed. That is what lets read and write share a line without a temporary — and it is a real difference from C, where the equivalent needs one.

Where the shape recurs

“Aggregate over everything to one side” covers a lot of ground once you look for it:

Product of array except self — a prefix pass and a suffix pass, multiplied.
Trapping rain water — max to the left and max to the right of each bar.
Best time to buy and sell stock — min to the left, running.
Next greater element — when the question is the nearest larger value rather than the largest, a running aggregate is not enough and you need a monotonic stack.

That last one is the useful boundary. A running value answers what is the biggest; it cannot answer which one comes first.