Problem Description
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.
Key Insights
- The last element of the array should always be replaced with -1 since there are no elements to its right.
- For any other element, we need to find the maximum value from the elements that come after it in the array.
- A reverse traversal of the array allows us to keep track of the maximum value seen so far, making the solution efficient.
Space and Time Complexity
Time Complexity: O(n) - We traverse the array once. Space Complexity: O(1) - We modify the array in place without using extra space.
Solution
To solve the problem, we can use a single pass from the end of the array to the beginning. We keep a variable to track the maximum element seen so far. For each element, we replace it with this maximum value and update the maximum if the current element is greater. The last element is set to -1 as specified.