Replace Elements With Greatest Element On Right Side Leetcode 1299 [Python]

Let’s get our hands dirty with some Arrays & Hashing coding with the Replace Elements With Greatest Element On Right Side LeetCode problem.

This problem falls under the, and is classified as an easy problem.

We will provide a Python solution to this problem and explain the reasoning behind our approach.

Problem Overview

The problem statement is as follows:

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

Let’s illustrate this with an example:

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 at index 1 (18).
Index 1: The greatest element to the right of index 1 is at index 4 (6).
Index 2: The greatest element to the right of index 2 is at index 4 (6).
Index 3: The greatest element to the right of index 3 is at index 4 (6).
Index 4: The greatest element to the right of index 4 is at index 5 (1).
Index 5: There are no elements to the right of index 5, so we put -1. Another example:

Example 2:

Input: arr = [400]
Output: [-1]

Explanation: In this case, there is only one element in the array, and there are no elements to the right of it, so it is replaced with -1.

Understanding Constraints

Before we dive into the solutions, let’s take a closer look at the constraints of the problem:

1 <= arr.length <= 10^4: The length of the input array arr can vary, but it will not exceed 10,000 elements.
1 <= arr[i] <= 10^5: Each element in the array is a positive integer, and they do not exceed 100,000.

Problem Solution

Bruteforce Approach

One way to solve this problem is through a brute force approach.

The idea is to iterate through the array, for each element, find the maximum element to its right, and replace it.

The last element is replaced with -1. This approach works, but it involves a lot of repeated work, leading to a time complexity of O(N^2), which is not efficient.

Let’s provide a Python code snippet for this brute force approach:

def replaceElements(arr):
    for i in range(len(arr) - 1):
        max_right = max(arr[i + 1:])
        arr[i] = max_right
    arr[-1] = -1
    return arr

Efficient Approach

To optimize the solution, we can observe that there’s a more efficient way to update the elements.

We can traverse the array in reverse order, keeping track of the maximum element we’ve encountered so far.

This way, we avoid redundant max computations and achieve a linear time complexity of O(N).

Here is the efficient Python solution:

def replaceElements(arr):
    right_max = -1  # Initialize the right maximum as -1
    for i in range(len(arr) - 1, -1, -1):
        new_max = max(right_max, arr[i])
        arr[i] = right_max
        right_max = new_max
    return arr

This efficient approach works by iterating through the array in reverse order, and at each step, it calculates the new maximum between the current element and the previous maximum (which is the maximum to the right).

This avoids the need to repeatedly compute the maximum values, making it an optimal solution for the problem.

Python Code Solution

Here’s the complete Python code solution for the problem:

View on GitHub ➹

def replaceElements(self, arr: List[int]) -> List[int]:
    right_max = -1  # Initialize the right maximum as -1
    for i in range(len(arr) - 1, -1, -1):
        new_max = max(right_max, arr[i])
        arr[i] = right_max
        right_max = new_max
    return arr

This code efficiently solves the problem, providing the expected output for the given input array.

Time and Space Complexity

Let’s analyze the time and space complexity of our efficient solution.

Time Complexity: The time complexity of the efficient solution is O(N), where N is the length of the input array arr.

We traverse the array once in reverse order, and at each step, we perform constant time operations.

Space Complexity: The space complexity is O(1) because we only use a constant amount of extra space to store the right_max and new_max variables.

We do not create any additional data structures that grow with the input size.

Reasoning Behind Our Approach

The reasoning behind our efficient approach is to optimize the solution by eliminating redundant work.

We observed that there’s no need to repeatedly compute the maximum values for each element in the array.

Instead, we can traverse the array in reverse order and, for each element, update it with the maximum value to its right.

By maintaining a right_max variable, we can efficiently compute the maximum for each element.

This approach reduces the time complexity from O(N^2) to O(N), making it a more efficient solution.

Conclusion

In this blog post, we tackled the LeetCode problem #1299, Replace Elements With Greatest Element On Right Side We provided both a brute force and an efficient Python solution to the problem, along with an explanation of the reasoning behind our approach.

The efficient solution, which traverses the array in reverse order, is the recommended approach as it optimizes the algorithm, resulting in a time complexity of O(N).

We hope this guide is helpful for beginners in coding and algorithm problem-solving.

If you have any questions, suggestions, or comments, please feel free to share them.

We encourage active participation and learning from the community.

You can find the original problem on LeetCode at the following link: Replace Elements With Greatest Element On Right Side.

Happy coding and problem-solving!