Replace Elements with Greatest Element on Right Side Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 3376

The problem Replace Elements with Greatest Element on Right Side Leetcode Solution provides us with an array or vector of integers. The problem asked us to replace all the elements with the element that is greatest among all the elements on the right side. So consider if we had an array or sequence, {a, b, c}. If the numbers follow the trend, b > c> a. So, as per the question, the output should be {b, c, -1}. Before diving deep into the solution, let’s check a few examples.

Replace Elements with Greatest Element on Right Side Leetcode Solution

[17,18,5,4,6,1]
[18,6,6,6,1,-1]

Explanation: The output is easy to understand because each element has been replaced by the greatest element on the right of it.

[400]
[-1]

Explanation: Since there is no element to the right of the current number. Thus we return -1 as output.

Approach for the Replace Elements with Greatest Element on Right Side Leetcode Solution

The problem states the problem clearly by its name itself. The problem says to replace each element with the greatest element that occurs on the right side of it. Now, the only that is left to do is to simulate the process. We can easily do this if we start traversing the array from the right side. So, instead of going from the left side, we start from the right side. We keep an element that stores the maximum element found until now. We store the current element in a variable, then keep on updating the maximum value. At this point, we can replace the current element with the greatest element/maximum element.

Code to Replace Elements with Greatest Element on Right Side Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

vector<int> replaceElements(vector<int>& arr) {
    int mx = -1, a;
    int n = arr.size();
    for (int i = n - 1; i >= 0; --i) {
        a = arr[i];
        arr[i] = mx;
        mx = max(mx, a);
    }
    return arr;
}

int main(){
    vector<int> arr = {17,18,5,4,6,1};
    vector<int> output = replaceElements(arr);
    for(int i=0;i<6;i++)
        cout<<output[i]<<" ";
}

18 6 6 6 1 -1

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
  public static int[] replaceElements(int[] arr) {
        int mx = -1, a;
        int n = arr.length;
        for (int i = n - 1; i >= 0; --i) {
            a = arr[i];
            arr[i] = mx;
            mx = Math.max(mx, a);
        }
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {17,18,5,4,6,1};
    int[] output = replaceElements(arr);
    for(int i=0;i<6;i++)
      System.out.print(output[i]+" ");
  }
}
18 6 6 6 1 -1

Complexity Analysis

Time complexity

O(N), since we traverse the array once. The time complexity is also linear.

Space Complexity

O(1), the algorithm is an in-place one and thus the space complexity is constant.

Translate »