1299. Replace Elements with Greatest Element on Right Side
Problem Description
In the given problem, we have an array called arr
. The task is to modify each element in this array, so that for each position in the array, you replace its value with the greatest value of the elements positioned to its right in the array. For the last element, since there are no elements to its right, you replace it with -1
. Finally, the modified array is returned.
Intuition
The intuitive approach to solving this problem is to start from the rightmost end of the array and move leftward. This way, at any given position i
, we will have already processed the elements to its right and thus would know the greatest element among them.
- We initialize a variable
m
to-1
, which will keep track of the maximum value we've encountered as we iterate the array from the right to left. - We start iterating from the end of the array.
- For the current element at index
i
, we store its value temporarily in a variablet
since it will be overwritten and we need to compare it againstm
afterward. - The current element at index
i
is then replaced with the maximum valuem
found so far. - We update
m
to be the maximum of the old maximumm
and the valuet
we saved before overwriting the element ati
. - We repeat these steps until all elements have been processed and return the modified array.
By the end of this process, each element is replaced by the maximum value to its right, and the last element has been correctly replaced with -1
.
Solution Approach
The solution uses a simple iterative approach without any complex data structures or additional space requirement (besides the input array). Here's a step-by-step explanation of the implementation details:
-
Initialize a variable
m
as-1
. This variable serves as a placeholder for the greatest element found so far to the right of the current index during the backward traversal of the array. -
Start a loop to traverse the array backwards. The loop starts from the last index, which is
len(arr) - 1
, moving towards the first index0
. We go backwards so that the rightmost elements get processed first. -
In each iteration, capture the current element before replacing it. The variable
t = arr[i]
is used to store the current value of the array at indexi
. -
In the next step, we replace the current element at index
i
with the greatest element on its rightm
. -
The last action in the iteration updates
m
to the maximum value between the previous maximumm
and the value we just replaced (t
). We use the built-inmax
function for this purpose:m = max(m, t)
. -
Continue this process until the loop finishes (all elements are checked).
-
Once the loop finishes, the modified array gets returned directly.
This is a linear time complexity O(n)
solution, where n
is the number of elements in the array. No additional space is used, making the space complexity O(1)
.
It's important to note that the implementation effectively overwrites each element in the array with the greatest value found to its right in a single pass, making it a highly efficient in-place algorithm.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example array arr = [4, 3, 2, 1]
to illustrate the solution approach described above.
-
Initialize
m
as-1
. This will hold the maximum value found to the right of the current element. -
Start traversing the array backwards:
- For
i = 3 (last index)
,arr[i]
is1
. We store this int
, and then we setarr[i]
to-1
, since it is the last element. - Update
m
tomax(m, t)
, which ismax(-1, 1)
, som
becomes1
.
- For
-
Move to
i = 2
:arr[i]
is2
. Store this int
, then setarr[i]
tom
, which is1
.- Update
m
tomax(m, t)
, which ismax(1, 2)
, som
becomes2
.
-
Move to
i = 1
:arr[i]
is3
. Store this int
, then setarr[i]
tom
, which is2
.- Update
m
tomax(m, t)
, which ismax(2, 3)
, som
becomes3
.
-
Finally, move to
i = 0
:arr[i]
is4
. Store this int
, then setarr[i]
tom
, which is3
.- Update
m
tomax(m, t)
, which ismax(3, 4)
, but since this is the last iteration, the value ofm
is no longer needed.
-
The loop has finished, and the modified array is now
arr = [3, 2, 1, -1]
.
The algorithm has successfully replaced each element with the maximum value among the elements positioned to its right, and the last element has been replaced with -1
. The whole process required only a single pass through the input array, making it a very efficient solution with a time complexity of O(n)
and a space complexity of O(1)
.
Solution Implementation
1class Solution:
2 def replaceElements(self, arr: List[int]) -> List[int]:
3 # Initialize the maximum value found to the right of the current element
4 max_to_the_right = -1
5
6 # Reverse iterate through the array
7 for i in range(len(arr) - 1, -1, -1):
8 # Store the current element before updating
9 current_element = arr[i]
10
11 # Replace the current element with the maximum value found so far
12 arr[i] = max_to_the_right
13
14 # Update the maximum value by comparing it with the previously stored current element
15 max_to_the_right = max(max_to_the_right, current_element)
16
17 # Return the modified array
18 return arr
19
20# The List type should be imported from the 'typing' module
21from typing import List
22
1class Solution {
2 public int[] replaceElements(int[] arr) {
3 // Start from the end of the array
4 int maxSoFar = -1; // Initially set the maximum to -1 since it will be the replacement for the last element
5
6 // Iterate through the array from the end to the beginning
7 for (int i = arr.length - 1; i >= 0; --i) {
8 int currentValue = arr[i]; // Store the current value to temporarily hold it
9 arr[i] = maxSoFar; // Replace the current element with the max of elements to its right
10 maxSoFar = Math.max(maxSoFar, currentValue); // Update the maxSoFar with the maximum between the maxSoFar and currentValue
11 }
12
13 // Return the modified array
14 return arr;
15 }
16}
17
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 std::vector<int> replaceElements(std::vector<int>& arr) {
7 int maxSoFar = -1; // Initially set the maximum to -1 since it will be the replacement for the last element
8
9 // Iterate through the array from the back to the front
10 for (int i = arr.size() - 1; i >= 0; --i) {
11 int currentValue = arr[i]; // Store the current value temporarily
12 arr[i] = maxSoFar; // Replace the current element with the max of elements to its right
13 maxSoFar = std::max(maxSoFar, currentValue); // Update maxSoFar to the maximum of maxSoFar and currentValue
14 }
15
16 // Return the modified array
17 return arr;
18 }
19};
20
1// Function to replace each element with the greatest element on its right side
2function replaceElements(arr: number[]): number[] {
3 // Start from the end of the array
4 let maxSoFar: number = -1; // Initially set the max to -1 because it will be the replacement for the last element
5
6 // Iterate through the array from the end to the start
7 for (let i = arr.length - 1; i >= 0; --i) {
8 // Temporarily hold the current value of the element
9 let currentValue: number = arr[i];
10 // Replace the current element with the greatest value to its right
11 arr[i] = maxSoFar;
12 // Update the maxSoFar to the maximum between the maxSoFar and currentValue
13 maxSoFar = Math.max(maxSoFar, currentValue);
14 }
15
16 // Return the modified array with replaced elements
17 return arr;
18}
19
Time and Space Complexity
Time Complexity
The provided function replaceElements
consists of a single loop that iterates backwards through the input list arr
. On each iteration, the function updates the current element with the maximum value found in the elements to the right of the current element. This loop runs exactly n
times where n
is the length of the list. Thus, the time complexity of the algorithm is O(n)
, where n
is the number of elements in arr
.
Space Complexity
The space complexity refers to the amount of extra space required by the algorithm. Since this function modifies the input list arr
in place and only uses a constant number of extra variables (t
and m
), the space complexity is O(1)
, which means it requires a constant additional space regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!