# 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

Aof sizeN. 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:

- The rightmost element of
`A`

will always be`-1`

There is no element at the right of the rightmost location. - When processing the element at index
`i`

all we need to do is substituting it with the maximum element found so far. - 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>& 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>& 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.

Be the first to leave a comment. Don’t be shy.