1299. Replace Elements With Greatest Element On Right Side - Explanation

Description

You are 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 = [2,4,5,3,1,2]

Output: [5,5,3,2,2,-1]

Example 2:

Input: arr = [3,3]

Output: [3,-1]

Constraints:

1 <= arr.length <= 10,000
1 <= arr[i] <= 100,000

Topics

Array

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Traversal - Iterating through arrays both forward and backward
Suffix Maximum Pattern - Maintaining a running maximum while traversing from right to left

1. Brute Force

Intuition

For each element at index i, we need to find the maximum value among all elements to its right. The most straightforward approach is to scan every element to the right for each position using index j. The last element has no elements to its right, so it becomes -1.

Algorithm

Create a result array ans of the same size as the input.
For each index i, initialize rightMax to -1.
Iterate through all indices j from i + 1 to the end, updating rightMax with the maximum value found.
Store rightMax in ans at position i.
Return the ans array.

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = [0] * n
        for i in range(n):
            rightMax = -1
            for j in range(i + 1, n):
                rightMax = max(rightMax, arr[j])
            ans[i] = rightMax
        return ans

public class Solution {
    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int rightMax = -1;
            for (int j = i + 1; j < n; j++) {
                rightMax = Math.max(rightMax, arr[j]);
            }
            ans[i] = rightMax;
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int rightMax = -1;
            for (int j = i + 1; j < n; ++j) {
                rightMax = max(rightMax, arr[j]);
            }
            ans[i] = rightMax;
        }
        return ans;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number[]}
     */
    replaceElements(arr) {
        let n = arr.length;
        let ans = new Array(n);
        for (let i = 0; i < n; i++) {
            let rightMax = -1;
            for (let j = i + 1; j < n; j++) {
                rightMax = Math.max(rightMax, arr[j]);
            }
            ans[i] = rightMax;
        }
        return ans;
    }
}

public class Solution {
    public int[] ReplaceElements(int[] arr) {
        int n = arr.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int rightMax = -1;
            for (int j = i + 1; j < n; j++) {
                rightMax = Math.Max(rightMax, arr[j]);
            }
            ans[i] = rightMax;
        }
        return ans;
    }
}

func replaceElements(arr []int) []int {
    n := len(arr)
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        rightMax := -1
        for j := i + 1; j < n; j++ {
            if arr[j] > rightMax {
                rightMax = arr[j]
            }
        }
        ans[i] = rightMax
    }
    return ans
}

class Solution {
    fun replaceElements(arr: IntArray): IntArray {
        val n = arr.size
        val ans = IntArray(n)
        for (i in 0 until n) {
            var rightMax = -1
            for (j in i + 1 until n) {
                rightMax = maxOf(rightMax, arr[j])
            }
            ans[i] = rightMax
        }
        return ans
    }
}

class Solution {
    func replaceElements(_ arr: [Int]) -> [Int] {
        let n = arr.count
        var ans = [Int](repeating: 0, count: n)
        for i in 0..<n {
            var rightMax = -1
            for j in (i + 1)..<n {
                rightMax = max(rightMax, arr[j])
            }
            ans[i] = rightMax
        }
        return ans
    }
}

impl Solution {
    pub fn replace_elements(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        let mut ans = vec![0; n];
        for i in 0..n {
            let mut right_max = -1;
            for j in (i + 1)..n {
                right_max = right_max.max(arr[j]);
            }
            ans[i] = right_max;
        }
        ans
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

The output array is not counted towards space complexity, as the standard convention measures only auxiliary working space.

2. Suffix Max

Intuition

By traversing right to left, we can maintain a running maximum of all elements seen so far in rightMax. When we visit position i, the current running maximum represents the greatest element to the right of i. We then update rightMax to include arr[i] for the next iteration. This eliminates redundant scanning.

Algorithm

Create a result array ans of the same size as the input.
Initialize rightMax to -1 (the value for the last position).
Traverse the array from right to left using index i.
For each index i, store the current rightMax in ans.
Update rightMax to be the maximum of itself and arr[i].
Return the ans array.

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = [0] * n
        rightMax = -1
        for i in range(n - 1, -1, -1):
            ans[i] = rightMax
            rightMax = max(arr[i], rightMax)
        return ans

public class Solution {
    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        int rightMax = -1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = rightMax;
            rightMax = Math.max(rightMax, arr[i]);
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n);
        int rightMax = -1;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = rightMax;
            rightMax = max(rightMax, arr[i]);
        }
        return ans;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number[]}
     */
    replaceElements(arr) {
        let n = arr.length;
        let ans = new Array(n);
        let rightMax = -1;
        for (let i = n - 1; i >= 0; i--) {
            ans[i] = rightMax;
            rightMax = Math.max(rightMax, arr[i]);
        }
        return ans;
    }
}

public class Solution {
    public int[] ReplaceElements(int[] arr) {
        int n = arr.Length;
        int[] ans = new int[n];
        int rightMax = -1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = rightMax;
            rightMax = Math.Max(arr[i], rightMax);
        }
        return ans;
    }
}

func replaceElements(arr []int) []int {
    n := len(arr)
    ans := make([]int, n)
    rightMax := -1
    for i := n - 1; i >= 0; i-- {
        ans[i] = rightMax
        if arr[i] > rightMax {
            rightMax = arr[i]
        }
    }
    return ans
}

class Solution {
    fun replaceElements(arr: IntArray): IntArray {
        val n = arr.size
        val ans = IntArray(n)
        var rightMax = -1
        for (i in n - 1 downTo 0) {
            ans[i] = rightMax
            rightMax = maxOf(rightMax, arr[i])
        }
        return ans
    }
}

class Solution {
    func replaceElements(_ arr: [Int]) -> [Int] {
        let n = arr.count
        var ans = [Int](repeating: 0, count: n)
        var rightMax = -1
        for i in stride(from: n - 1, through: 0, by: -1) {
            ans[i] = rightMax
            rightMax = max(rightMax, arr[i])
        }
        return ans
    }
}

impl Solution {
    pub fn replace_elements(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        let mut ans = vec![0; n];
        let mut right_max = -1;
        for i in (0..n).rev() {
            ans[i] = right_max;
            right_max = right_max.max(arr[i]);
        }
        ans
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

The output array is not counted towards space complexity, as the standard convention measures only auxiliary working space.

Common Pitfalls

Traversing Left to Right

Processing the array from left to right requires recalculating the maximum of all right elements for each position, resulting in O(n^2) time complexity. The optimal approach traverses right to left, maintaining a running maximum in a single pass.

Updating the Maximum Before Storing the Result

When traversing right to left, the current element's value must be stored in the result before updating rightMax. Updating rightMax first causes the current element to incorrectly include itself in its own replacement value.