Replace Elements with Greatest Element on Right Side
EasyPrompt
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] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses nested loops to solve the problem. The outer loop iterates through each element of the array that needs to be replaced. For each of these elements, an inner loop scans all subsequent elements to find the greatest one among them.
Algorithm
- Get the length of the array,
n. - Iterate through the array with an outer loop from
i = 0ton - 2. - For each element
arr[i], initialize a variablemax_valto be the first element on its right,arr[i+1]. - Start an inner loop from
j = i + 2ton - 1. - In the inner loop, update
max_valby comparing it witharr[j]:max_val = Math.max(max_val, arr[j]). - After the inner loop finishes, the
max_valholds the greatest element to the right ofarr[i]. Replacearr[i]withmax_val. - After the outer loop completes, all elements except the last one are updated. Set the last element
arr[n - 1]to-1. - Return the modified array.
Walkthrough
The brute-force method directly translates the problem statement into code. We iterate through the array from the first element up to the second-to-last element. For each element at index i, we perform a search on the subarray to its right (from i+1 to the end) to find the maximum value. Once this maximum value is found, we replace the element at index i with it. This process is repeated for all elements. Finally, since the last element has no elements to its right, it is replaced with -1 as per the problem's requirement. While simple to conceptualize, this method involves a lot of redundant calculations, as the search for the maximum is repeated for overlapping subarrays.
class Solution { public int[] replaceElements(int[] arr) { int n = arr.length; if (n == 0) { return arr; } for (int i = 0; i < n - 1; i++) { int maxVal = arr[i + 1]; for (int j = i + 2; j < n; j++) { if (arr[j] > maxVal) { maxVal = arr[j]; } } arr[i] = maxVal; } arr[n - 1] = -1; return arr; }}Complexity
Time
O(n^2), where n is the length of the array. The outer loop runs n-1 times, and for each iteration, the inner loop can run up to n-1 times. This results in a quadratic number of comparisons.
Space
O(1). The replacement is done in-place, and only a few variables are used for loops and storing the maximum value, so the extra space is constant.
Trade-offs
Pros
Straightforward to understand and implement as it directly follows the problem's definition.
It modifies the array in-place, requiring no extra space proportional to the input size.
Cons
Highly inefficient due to its O(n^2) time complexity.
For large inputs (as allowed by the constraints, up to 10^4), this approach will be too slow and likely result in a 'Time Limit Exceeded' error on coding platforms.
A much more efficient solution involves a single pass through the array from right to left. By traversing in reverse, we can keep track of the maximum element seen so far. This maximum is precisely the value needed for the element to its immediate left.
Algorithm
- Initialize a variable
maxFromRightto-1. This variable will store the greatest element encountered so far as we traverse from the right. - Get the length of the array,
n. - Iterate through the array in reverse order, from index
i = n - 1down to0. - Inside the loop, for each element
arr[i], store its original value in a temporary variable, e.g.,currentElement = arr[i]. - Replace the current element
arr[i]with the current value ofmaxFromRight. At this point,maxFromRightholds the greatest element to the right of the originalarr[i]. - Update
maxFromRightto be the maximum of its current value and thecurrentElementwe just processed:maxFromRight = Math.max(maxFromRight, currentElement). - After the loop finishes, the array is correctly modified. Return
arr.
Walkthrough
This optimal approach cleverly avoids redundant computations by iterating backward. We start from the rightmost element. The greatest element to its right is non-existent, so we know its replacement is -1. We can initialize a variable, maxFromRight, to -1. Then, we iterate from the last index n-1 down to 0. At each index i, the current maxFromRight is the answer for arr[i]. Before moving to the next element on the left (i-1), we update maxFromRight by comparing it with the original value of arr[i]. This way, as we move left, maxFromRight always holds the maximum of all elements we have visited so far (which are the elements to the right of the current position). This allows us to update the array in a single pass.
class Solution { public int[] replaceElements(int[] arr) { int n = arr.length; int maxFromRight = -1; for (int i = n - 1; i >= 0; i--) { // Store the original value of the current element int currentElement = arr[i]; // Replace the current element with the max found so far from the right arr[i] = maxFromRight; // Update the max from the right for the next element to the left maxFromRight = Math.max(maxFromRight, currentElement); } return arr; }}Complexity
Time
O(n), where n is the length of the array. We iterate through the array only once.
Space
O(1). The algorithm uses only a couple of variables (`maxFromRight`, `currentElement`) regardless of the input array size. The modification is done in-place.
Trade-offs
Pros
Extremely efficient with a linear time complexity of O(n).
Optimal space complexity of O(1) as it modifies the array in-place.
It is the most performant solution for this problem.
Cons
The logic of iterating from right to left and updating the maximum value might be slightly less intuitive to grasp initially compared to the straightforward brute-force approach.
Solutions
Solution
class Solution {public int[] replaceElements(int[] arr) { for (int i = arr.length - 1, max = -1; i >= 0; --i) { int t = arr[i]; arr[i] = max; max = Math.max(max, t); } return arr; }}class Solution {public: vector<int> replaceElements(vector<int> &arr) { for (int i = arr.size() - 1, mx = -1; ~i; --i) { int x = arr[i]; arr[i] = mx; mx = max(mx, x); } return arr; }};class Solution: def replaceElements(self, arr: List[int]) -> List[int]: m = - 1 for i in range(len(arr) - 1, - 1, - 1): t = arr[i] arr[i] = m m = max(m, t) return arrVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.