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] <= 105In #1299 Replace Elements with Greatest Element on Right Side, each element in the array must be replaced by the greatest element that appears to its right, while the last element becomes -1. A straightforward idea is to check all elements to the right of every index to find the maximum. However, this leads to repeated work and results in an inefficient O(n^2) approach.
A more optimal strategy uses reverse traversal. Instead of searching the right side repeatedly, iterate from the end of the array while maintaining the maximum value seen so far. For each position, replace the current value with this running maximum, then update the maximum if the original value is larger. This technique avoids nested loops and processes each element only once.
This approach is efficient because it uses a single pass and only a few variables, achieving linear time complexity with constant extra space. It is a common interview pattern for array problems that require knowledge of future elements.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reverse Traversal with Running Maximum | O(n) | O(1) |
| Brute Force (check right side for each element) | O(n^2) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Loop through the array starting from the end.
Keep the maximum value seen so far.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Reverse traversal works well because the problem depends on values that appear to the right of each element. By moving from the end toward the start, you always know the maximum value among the elements already processed.
Yes, variations of this problem appear in coding interviews because it tests array traversal patterns and optimization thinking. Interviewers often use it to check whether candidates can replace a brute-force approach with a linear-time strategy.
No complex data structure is required for this problem. A simple array traversal with a variable to track the current maximum on the right is sufficient. This keeps the solution both efficient and easy to implement.
The optimal approach is to traverse the array from right to left while maintaining the maximum value seen so far. At each step, replace the current element with this running maximum and update the maximum if needed. This allows the problem to be solved in linear time.