Replace Elements with Greatest Element on Right Side | LeetCode

Question link : Replace Elements with Greatest Element on Right Side

What the question wants ?

The question is about in place operation on array. Here an array is given with some values and we have to do some operations described with the question. The operation are little hard to understand but if got the logic behind it then the question will become too easy to solve. As per the operation we just have to replace the values of array elements with the maximum of all the values on its right side 

ex. 

if the elements are  6,4,2,4,9,3  then consider 2 as our current element and then maximum value on its right is 9, and just like this for 6 maximum on its right is 9.

Now we know what we have to do. 

Logic behind the Solution Code:

There can be many ways to solve this question but we will discuss one of them here.

Solution 1:

Here Iterate from the end till start to get the maximum on its right.

We initialized max = -1, where max represent the maximum element on its right. 

Each round, we set A[i] = max , to set the new value over the previous.

Update max = Math.max(max, A[i]), to set the maximum of A[i] and max into max.

Complexity :

Time O(N)

Space O(1)

Code :

Java:

    public int[] replaceElements(int[] A) {

        for (int i = A.length - 1, mx = -1; i >= 0; --i)

            mx = Math.max(A[i], A[i] = mx);

        return A;

    }

Java, expanded version:

    public int[] replaceElements2(int[] A) {

        int mx = -1, n = A.length, a;

        for (int i = n - 1; i >= 0; --i) {

            a = A[i];

            A[i] = mx;

            mx = Math.max(mx, a);

        }

        return A;

    }