Transform array such that each element contains the greatest element on its right side

Problem statement

In this article we will be discussing how to solve an easy problem that has been asked at Amazon coding interviews. This is a must do problem for your coding interview preparation. The problem statement goes as follows:

You are given an array A of size N. You have to modify A in place s.t. A[i] = M where M is the maximum value among all elements A[j], j > i. If such element does not exists set A[i] = -1.

Example

Input :  A = {15, 22, 12, 13, 12, 19, 0, 2}
Output : A = {22, 19, 19, 19, 19, 2, 2, -1}

Input :  A = {2, 3, 1, 9}
Output : A = {9, 9, 9, -1}

---

Solution

Since this is a quite easy problem, we need to focus on making a good impression on the interviewer by showing a clean reasoning and elegant code implementation of the solution.

Let's start by outlining our solution:

1. The rightmost element of A will always be -1 There is no element at the right of the rightmost location.
2. When processing the element at index i all we need to do is substituting it with the maximum element found so far.
3. We need to make sure that at each iteration we keep track of what is the maximum element so far.

---

C++ Code

The ideas above can be coded as follows:

void solve(std::vector<int>&amp; V)
{
    if(V.size() <=0 )
        return;
    //max so far
    int M = -1;
    int i = V.size()-1;
    do{
        const int m = max(M,V[i]);
        V[i] = M;
        M = m;
        i--;
    }while(i >= 0);
}

Another alternative and cleaner implementation is given below:

void solve(std::vector<int>&amp; V)
{
    if(V.size() > 0 )
    {       
        V.back() = -1;
        for(int i = V.size()-2, M = V.back(); i >=0; i--){
            const int m = max(M,V[i]);
            V[i] = M;
            M = m;
        }
    }
}

The time and space complexity of the code above is linear in the length of A.

---

If you liked this article and you want to read more about coding interview preparation, take a look at the previous article of the series.