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.
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.
Constraints:
1 <= arr.length <= 1041 <= arr[i] <= 105Problem Overview: You are given an integer array arr. For every index, replace the value with the greatest element that appears to its right. The last element has no elements to its right, so it becomes -1. The goal is to compute the transformation efficiently.
Approach 1: Brute Force Approach (Time: O(n^2), Space: O(1))
For each index i, scan the subarray from i+1 to the end and compute the maximum value. Replace arr[i] with that maximum. The final element is set to -1. This method relies purely on repeated traversal of the array, making it straightforward to reason about but inefficient for large inputs.
The key drawback is repeated work. Every element recomputes the maximum of the suffix even though nearby elements share most of the same suffix values. That repeated scanning results in quadratic time complexity.
Approach 2: Reverse Iteration Approach (Time: O(n), Space: O(1))
The optimal solution processes the array from right to left while maintaining the maximum value seen so far. Start with maxRight = -1. For each index moving backward, store the current element, replace it with maxRight, then update maxRight = max(maxRight, originalValue).
This works because when you traverse from the end, maxRight always represents the largest element among all elements to the right of the current index. Each element is processed exactly once, and the algorithm only stores a single running maximum. The technique is common in array problems where suffix information is needed without extra memory.
The approach modifies the array in-place and avoids additional data structures. It behaves similarly to a suffix maximum computation often seen in prefix/suffix style array problems.
Recommended for interviews: Interviewers expect the reverse iteration solution. It shows you recognize that the maximum of the suffix can be maintained incrementally instead of recomputed. Starting with the brute force idea demonstrates understanding of the requirement, but transitioning to the O(n) reverse traversal shows strong optimization instincts in array manipulation problems.
This approach iterates over the array starting from the end toward the beginning. By doing so, we can keep a running track of the maximum element found so far on the right side. This method allows us to update each element in a single pass efficiently.
In this C code, we iterate from the end of the array, keeping track of the maximum value seen so far. We replace each index with the maximum collected, starting with -1 for the last element.
Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(1), as the operation is done in-place with a constant extra space.
This approach involves nested loops, where for each element, we check its following elements to find the greatest and update it. Although this is not the most efficient approach, it's easier to understand.
This C implementation uses a brute force method where each element's right subarray is checked to find the maximum element, thus resulting in a higher time complexity.
Time Complexity: O(n^2) because of the nested loops over the array.
Space Complexity: O(1)
We use a variable mx to record the maximum value to the right of the current position, initially mx = -1.
Then we traverse the array from right to left. For each position i, we denote the current value as x, update the current position's value to mx, and then update mx = max(mx, x).
Finally, return the original array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Reverse Iteration Approach | Time Complexity: O(n) where n is the number of elements in the array. |
| Brute Force Approach | Time Complexity: O(n^2) because of the nested loops over the array. |
| Reverse Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Approach | O(n^2) | O(1) | Useful for understanding the problem or when constraints are very small. |
| Reverse Iteration Approach | O(n) | O(1) | Best choice for interviews and production. Maintains a running suffix maximum while traversing from right to left. |
Leetcode 1299 - REPLACE ELEMENTS WITH GREATEST ELEMENT ON RIGHT SIDE • NeetCode • 71,428 views views
Watch 9 more video solutions →Practice Replace Elements with Greatest Element on Right Side with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor