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.
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; }}Video 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.