1299. Replace Elements with Greatest Element on Right Side

EasyArray
Leetcode Link

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.

  1. 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.
  2. We start iterating from the end of the array.
  3. For the current element at index i, we store its value temporarily in a variable t since it will be overwritten and we need to compare it against m afterward.
  4. The current element at index i is then replaced with the maximum value m found so far.
  5. We update m to be the maximum of the old maximum m and the value t we saved before overwriting the element at i.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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:

  1. 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.

  2. Start a loop to traverse the array backwards. The loop starts from the last index, which is len(arr) - 1, moving towards the first index 0. We go backwards so that the rightmost elements get processed first.

  3. 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 index i.

  4. In the next step, we replace the current element at index i with the greatest element on its right m.

  5. The last action in the iteration updates m to the maximum value between the previous maximum m and the value we just replaced (t). We use the built-in max function for this purpose: m = max(m, t).

  6. Continue this process until the loop finishes (all elements are checked).

  7. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider an example array arr = [4, 3, 2, 1] to illustrate the solution approach described above.

  1. Initialize m as -1. This will hold the maximum value found to the right of the current element.

  2. Start traversing the array backwards:

    • For i = 3 (last index), arr[i] is 1. We store this in t, and then we set arr[i] to -1, since it is the last element.
    • Update m to max(m, t), which is max(-1, 1), so m becomes 1.

  3. Move to i = 2:

    • arr[i] is 2. Store this in t, then set arr[i] to m, which is 1.
    • Update m to max(m, t), which is max(1, 2), so m becomes 2.

  4. Move to i = 1:

    • arr[i] is 3. Store this in t, then set arr[i] to m, which is 2.
    • Update m to max(m, t), which is max(2, 3), so m becomes 3.

  5. Finally, move to i = 0:

    • arr[i] is 4. Store this in t, then set arr[i] to m, which is 3.
    • Update m to max(m, t), which is max(3, 4), but since this is the last iteration, the value of m is no longer needed.

  6. 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
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫