Replace Elements with Greatest Element on Right Side
EasyAsked by:
17 views
Topics:
Arrays
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the expected behavior if the input array is null or empty?
- Can the array contain negative numbers, zeros, or only positive integers?
- What is the expected output when processing the last element of the array? Should it be replaced with -1 as in the example?
- What is the maximum size of the input array? I want to understand any potential memory constraints.
- Is the input array guaranteed to be an array of integers, or could it contain other data types?
Brute Force Solution
Approach
The brute force method for this problem involves looking at each position one at a time. For each position, we'll find the largest value among all the elements that come after it, and then replace the value at that position with that largest value.
Here's how the algorithm would work step-by-step:
- Start at the very first spot.
- Look at all the spots after it, all the way to the end.
- Find the biggest number among those spots you just looked at.
- Replace the number in the very first spot with that biggest number you found.
- Now, move to the second spot.
- Again, look at all the spots after the second spot, going all the way to the end.
- Find the biggest number among *those* spots.
- Replace the number in the second spot with this new biggest number.
- Keep doing this, moving one spot at a time, until you get to the second-to-last spot.
- When you get to the very last spot, replace it with negative one.
Code Implementation
def replace_elements_brute_force(numbers):
list_length = len(numbers)
for current_index in range(list_length - 1):
maximum_value = -1
# Find max from current to the end
for comparison_index in range(current_index + 1, list_length):
maximum_value = max(maximum_value, numbers[comparison_index])
numbers[current_index] = maximum_value
# The last element is always -1, per problem statement
numbers[list_length - 1] = -1
return numbersBig(O) Analysis
Time Complexity
O(n²) – The outer loop iterates through each of the n elements of the input array. For each element, the inner part of the algorithm searches for the largest element in the remaining portion of the array to the right. In the worst case, finding the maximum element requires iterating through almost the entire array again, giving a cost of approximately n operations for each of the n outer iterations. Therefore, the total number of operations can be represented as approximately n * n/2, which simplifies to O(n²).
Space Complexity
O(1) – The brute force method described iterates through the input array in place, modifying the array elements directly. It doesn't create any additional data structures like temporary arrays or hash maps. Therefore, the algorithm uses a constant amount of extra space, regardless of the input size N, where N is the number of elements in the input array.
Optimal Solution
Approach
The most efficient way is to start from the end and work backward. We keep track of the biggest number we've seen so far as we move left, updating each spot along the way.
Here's how the algorithm would work step-by-step:
- Begin at the very last position in the sequence.
- Store the number at the last position as the current largest number.
- Replace the number at the last position with -1, since there's nothing to its right.
- Move one position to the left.
- Remember the current number, then check to see if it is greater than the stored largest number.
- If the current number is greater than the stored largest number, replace the stored largest number with the current number.
- Replace the current position with the stored largest number.
- Continue this process, moving left one position at a time until you reach the beginning.
Code Implementation
def replace_elements(array):
current_greatest = -1
# Iterate backwards
for i in range(len(array) - 1, -1, -1):
# Store current element
current_element = array[i]
# Replace current with greatest
array[i] = current_greatest
# Update greatest if needed
if current_element > current_greatest:
# New greatest found
current_greatest = current_element
return arrayBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the input array of size n exactly once, starting from the end and moving towards the beginning. In each iteration, it performs a constant amount of work: updating the maximum value seen so far and replacing the current element. Since the number of operations grows linearly with the input size n, the time complexity is O(n).
Space Complexity
O(1) – The provided solution operates in-place, meaning it modifies the input array directly without creating significant auxiliary data structures. The algorithm primarily uses a single variable, the 'stored largest number', to keep track of the greatest element encountered so far. Since the memory used by this variable remains constant irrespective of the input array's size (N), the auxiliary space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty array input | Return an empty array as specified since no replacement is possible. |
| Array with a single element | Replace the single element with -1 as the rightmost element has no right neighbor. |
| Array with maximum possible integer value repeated multiple times | The algorithm should handle the maximum integer value without overflow, correctly identifying the maximum to the right. |
| Array with minimum possible integer value repeated multiple times | The algorithm should handle the minimum integer value without issue, correctly identifying the maximum to the right. |
| Array containing a mix of positive, negative, and zero values | The algorithm compares all elements regardless of their sign, finding the correct maximum to the right. |
| Array with values already in descending order | The algorithm correctly replaces each element with the next smaller value, culminating in -1 for the last. |
| Large input array (performance) | The solution should iterate through the array efficiently in reverse, so time complexity should be O(n). |
| Input array is null | Return null or throw an IllegalArgumentException as appropriate, according to the problem constraints or API definition. |
Empty array input
How to Handle:
Return an empty array as specified since no replacement is possible.
Array with a single element
How to Handle:
Replace the single element with -1 as the rightmost element has no right neighbor.
Array with maximum possible integer value repeated multiple times
How to Handle:
The algorithm should handle the maximum integer value without overflow, correctly identifying the maximum to the right.
Array with minimum possible integer value repeated multiple times
How to Handle:
The algorithm should handle the minimum integer value without issue, correctly identifying the maximum to the right.
Array containing a mix of positive, negative, and zero values
How to Handle:
The algorithm compares all elements regardless of their sign, finding the correct maximum to the right.
Array with values already in descending order
How to Handle:
The algorithm correctly replaces each element with the next smaller value, culminating in -1 for the last.
Large input array (performance)
How to Handle:
The solution should iterate through the array efficiently in reverse, so time complexity should be O(n).
Input array is null
How to Handle:
Return null or throw an IllegalArgumentException as appropriate, according to the problem constraints or API definition.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
