LeetCode 1299 - Replace Elements with Greatest Element on Right Side

The problem gives us an integer array arr and asks us to replace every element with the greatest value that appears some

leetcodeeasyarray

LeetCode Problem 1299

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us an integer array arr and asks us to replace every element with the greatest value that appears somewhere to its right. The final element in the array has no elements to its right, so it must always become -1.

In other words, for every index i, we want to compute:

  • the maximum value among all elements from i + 1 to the end of the array
  • replace arr[i] with that value

The last index has no valid range to examine, so its replacement value is -1.

For example, consider:

arr = [17,18,5,4,6,1]

For index 0, the elements to the right are [18,5,4,6,1], and the maximum is 18.

For index 1, the elements to the right are [5,4,6,1], and the maximum is 6.

Continuing this process produces:

[18,6,6,6,1,-1]

The constraints are relatively small:

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

An O(n^2) solution would technically still pass for 10^4 in many environments, but it is inefficient and unnecessary. The problem has a clean linear-time solution.

Several edge cases are important:

  • A single-element array such as [400]
  • Arrays already in decreasing order
  • Arrays already in increasing order
  • Arrays where many elements are equal
  • Very small arrays where index handling mistakes are common

The problem guarantees that the array contains at least one element, so we never need to handle an empty array.

Approaches

Brute Force Approach

The most direct solution is to process each index independently.

For every position i, we scan all elements to the right of i and compute the maximum value manually. After finding that maximum, we store it as the replacement value for arr[i].

For the last index, we simply assign -1.

This approach is correct because it explicitly checks every valid candidate to the right of each position. However, it repeatedly scans overlapping portions of the array.

For example:

Index 0 scans almost the entire array
Index 1 scans almost the entire remaining array
Index 2 scans slightly less

This repeated work leads to quadratic time complexity.

Optimal Approach

The key observation is that the maximum value to the right of an index can be maintained incrementally if we process the array from right to left.

Suppose we are standing at index i.

If we already know the greatest value seen so far among elements to the right, then:

  • that value is exactly what arr[i] should become
  • after processing index i, we update the running maximum using the original value at arr[i]

This works because when traversing from right to left, we always have complete information about everything to the right of the current index.

Instead of rescanning the suffix repeatedly, we maintain one variable:

max_right

This variable always stores the greatest value encountered so far while moving backward through the array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) For each index, scan all elements to the right
Optimal O(n) O(1) Traverse from right to left while maintaining running maximum

Algorithm Walkthrough

  1. Initialize a variable called max_right to -1.

This variable represents the greatest element seen so far to the right of the current position. We start with -1 because the last element should become -1. 2. Traverse the array from right to left.

We move backward because each position depends on information from its right side. By the time we reach an index, we already know the maximum value among all later elements. 3. Store the current element temporarily.

Before overwriting arr[i], we must save its original value because it may become the new maximum for elements further left. 4. Replace arr[i] with max_right.

At this moment, max_right contains the largest value among all elements strictly to the right of index i. 5. Update max_right.

Compare the saved original value with the current max_right and keep the larger one. 6. Continue until the beginning of the array is reached.

Every element will eventually contain the greatest value to its right.

Why it works

The algorithm maintains an invariant:

Before processing index i,
max_right equals the maximum value among all elements to the right of i.

Because we process indices from right to left, this invariant is always true. We use max_right as the replacement value, then update it using the original current element so the invariant remains valid for the next iteration.

This guarantees correctness for every index.

Python Solution

from typing import List

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_right = -1

        for i in range(len(arr) - 1, -1, -1):
            current = arr[i]
            arr[i] = max_right
            max_right = max(max_right, current)

        return arr

The implementation follows the optimal right-to-left traversal strategy.

The variable max_right tracks the largest value encountered so far while moving backward through the array. Initially, it is -1 because the last element must become -1.

The loop iterates from the final index down to index 0. For each position:

  • the original value is stored in current
  • the array element is replaced with max_right
  • max_right is updated using the original value

Saving the original value before overwriting is essential. Otherwise, we would lose information needed to update the running maximum.

The solution modifies the array in place, which keeps the space complexity constant.

Go Solution

func replaceElements(arr []int) []int {
    maxRight := -1

    for i := len(arr) - 1; i >= 0; i-- {
        current := arr[i]
        arr[i] = maxRight

        if current > maxRight {
            maxRight = current
        }
    }

    return arr
}

The Go implementation is almost identical to the Python version.

Slices in Go are mutable, so the function updates the input slice directly. No additional array allocation is required.

There are no integer overflow concerns because the constraints are very small compared to Go's integer range.

The algorithm also naturally handles single-element arrays because the loop runs once, replacing the only value with -1.

Worked Examples

Example 1

Input:

arr = [17,18,5,4,6,1]

Initial state:

max_right = -1
Index Original Value max_right Before New Value max_right After Array State
5 1 -1 -1 1 [17,18,5,4,6,-1]
4 6 1 1 6 [17,18,5,4,1,-1]
3 4 6 6 6 [17,18,5,6,1,-1]
2 5 6 6 6 [17,18,6,6,1,-1]
1 18 6 6 18 [17,6,6,6,1,-1]
0 17 18 18 18 [18,6,6,6,1,-1]

Final result:

[18,6,6,6,1,-1]

Example 2

Input:

arr = [400]

Initial state:

max_right = -1
Index Original Value max_right Before New Value max_right After Array State
0 400 -1 -1 400 [-1]

Final result:

[-1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only a few extra variables are used

The algorithm performs a single traversal of the array from right to left. Each iteration does constant work, so the total running time grows linearly with the input size.

No auxiliary data structures are allocated. The input array itself is modified in place, which keeps the extra memory usage constant.

Test Cases

from typing import List

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_right = -1

        for i in range(len(arr) - 1, -1, -1):
            current = arr[i]
            arr[i] = max_right
            max_right = max(max_right, current)

        return arr

solution = Solution()

assert solution.replaceElements([17, 18, 5, 4, 6, 1]) == [18, 6, 6, 6, 1, -1]  # Provided example
assert solution.replaceElements([400]) == [-1]  # Single-element array
assert solution.replaceElements([1, 2, 3, 4]) == [4, 4, 4, -1]  # Strictly increasing
assert solution.replaceElements([4, 3, 2, 1]) == [3, 2, 1, -1]  # Strictly decreasing
assert solution.replaceElements([7, 7, 7, 7]) == [7, 7, 7, -1]  # All equal values
assert solution.replaceElements([10, 5]) == [5, -1]  # Two-element array
assert solution.replaceElements([5, 10]) == [10, -1]  # Increasing two-element array
assert solution.replaceElements([100000, 1, 2]) == [2, 2, -1]  # Large value at front
assert solution.replaceElements([1, 100000, 2]) == [100000, 2, -1]  # Large middle value
assert solution.replaceElements([9]) == [-1]  # Minimum valid length
Test Why
[17,18,5,4,6,1] Validates the main example
[400] Tests single-element handling
[1,2,3,4] Tests increasing order
[4,3,2,1] Tests decreasing order
[7,7,7,7] Tests duplicate values
[10,5] Tests small decreasing array
[5,10] Tests small increasing array
[100000,1,2] Tests large front value
[1,100000,2] Tests large middle value
[9] Tests smallest possible input size

Edge Cases

Single-Element Array

A one-element array is the smallest valid input. Since there are no elements to the right, the answer must always be [-1].

This case often causes bugs in solutions that assume at least one right-side element exists. The implementation handles it naturally because the loop runs once with max_right = -1.

Strictly Increasing Array

Consider:

[1,2,3,4]

Every element should become the final element 4, except the last position.

This case is important because the running maximum changes repeatedly while traversing backward. The algorithm correctly updates max_right after each step.

Strictly Decreasing Array

Consider:

[4,3,2,1]

Each element's replacement is simply the next element to its right.

This case verifies that the algorithm does not incorrectly keep outdated maximum values. Since the running maximum changes at every step, correctness depends on proper update order.

Arrays with Duplicate Values

Consider:

[7,7,7,7]

The greatest value to the right remains 7 for all positions except the last.

Some incorrect implementations accidentally use strictly greater comparisons in a way that mishandles duplicates. This implementation uses max() correctly, so equal values are preserved properly.