#1299

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Replace Elements with Greatest Element on Right Side

Replace every element in an array with the greatest element on its right side, and replace the last element with -1.

Problem Statement

You are given an array arr of integers. Your task is to replace each element with the greatest element to its right. For the last element, set it to -1 as there are no elements to its right.

Return the modified array. For example, given arr = [17,18,5,4,6,1], the expected output is [18,6,6,6,1,-1]. The greatest elements are selected by comparing elements from right to left.

Examples

Example 1

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

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

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]

There are no elements to the right of index 0.

Constraints

1 <= arr.length <= 104
1 <= arr[i] <= 105

Solution Approach

Array-driven approach

To solve the problem efficiently, iterate through the array starting from the last element. Keep track of the greatest element encountered as you move leftward. For each element, update it with the maximum value seen to its right, and adjust the value of the last element to -1.

Time Complexity Consideration

The time complexity is linear, O(n), because the array is traversed only once. This ensures the solution is efficient even for large input sizes, as we do not need to use nested loops or extra arrays.

Space Optimization

The solution can be implemented in-place, requiring only constant space O(1). This makes the algorithm space-efficient since it modifies the array directly without needing additional data structures.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we iterate through the array once, and the space complexity is O(1) because we are modifying the array in place without using extra space.

What Interviewers Usually Probe

Tests understanding of array traversal and modification in-place.
Checks if the candidate is aware of optimizing both time and space complexities.
Assesses ability to handle edge cases like single-element arrays and no right elements.

Common Pitfalls or Variants

Common pitfalls

Not accounting for the last element, which must be replaced with -1.
Confusing the order of operations when updating the elements from right to left.
Using unnecessary extra space when the problem can be solved in-place.

Follow-up variants

Handling arrays with only one element.
Modifying the problem to work with arrays of floating-point numbers.
Implementing the solution with additional constraints such as negative numbers.

FAQ

What is the best approach to solve 'Replace Elements with Greatest Element on Right Side'?

The optimal solution uses a backward traversal of the array, keeping track of the maximum value encountered, and modifying the array in-place.

How do I handle the last element in the array?

The last element should be replaced with -1, as there are no elements to its right.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array, as the array is traversed only once.

Can this problem be solved with extra space?

Yes, but the optimal solution modifies the array in-place to achieve O(1) space complexity.

How can I modify the solution for arrays with negative numbers?

The solution works the same way for arrays with negative numbers; the greatest element to the right is still the key criterion.

terminal

Solution

Solution 1: Reverse Traversal

We use a variable $mx$ to record the maximum value to the right of the current position, initially $mx = -1$.

1

2

3

4

5

6

7

8

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        mx = -1
        for i in reversed(range(len(arr))):
            x = arr[i]
            arr[i] = mx
            mx = max(mx, x)
        return arr

Continue Practicing

#1298 maximum candies you can get from boxes #1300 sum of mutated array closest to target #1301 number of paths with max score