Coding interview Essentials

6. Greatest element on the right side

Greatest element on the right side

Introduction

This chapter discusses a farily common problem asked during the on-site interview at Amazon.

Problem statement

You are given an array \(A\) of size \(n\). You have to modify \(A\) in place s.t. \(A[i] = max(A[i+1], A[i+2],\ldots, A[n-1])\). In other words \(A[i]\) should be substituted with the maximum value among all elements \(A[j], j > i\). If such element does not exists set \(A[i] = -1\).


Given the input array \(A = \{15, 22, 12, 13, 12, 19, 0, 2\}\), the output of the function in this case shluld be \(A = \{22, 19, 19, 19, 19, 2, 2, -1\}\).


Given the input array \(A = \{2, 3, 1, 9\}\), the output of the function in this case shluld be \(A = \{9, 9, 9, -1\}\).

Clarification Questions

Are the element of the array sorted?

No, the input array is not sorted.

Are the element always positive or negative?

The elements can be either positive or negative.

Discussion

Since this is a quite an easy problem, hence it is very important to to focus on making a good impression on the interviewer by showing a clean reasoning and elegant implementation of the solution. This problem is considered not very challengind because it already has all the information required to solve it in its statement.

Brute Force

As usual one should always start talking to the interviewer right away about the bruteforce solution which in this case is quite straightforward. All it is necessary is scanning the array from left ro right and for each element finding the greatest element among all the elements on its right. This can be very easily implemented in C++ using the std::max_element() function as shown in Listing [list::greatest_right_bruteforce]. Note how the search on the right side is enforced by using as starting point \(begin(A)+i+1\) for the range in the std::max_element() function.

Listing 1: C++ bruteforce solution to the problem of modifying an array in place with the greatest element on the right side.

void greatest_right_bruteforce(std::vector<int> &A)
{
  for (size_t i = 0; i < A.size(); i++)
  {
    const auto greatest = max_element(begin(A) + i + 1, end(A));
    A[i]                = (greatest != end(A)) ? *greatest : -1;
  }
}

Note also that the last element will always be modified into \(-1\) because, it is the only element which does not have any element on its right side and according to the statement in this case it should be modified into \(-1\).

This solution is considered poor because it has a time complexity of \(O(n^2)\) and a linear solution exists.

Linear solution

The approach used in Listing [list::greatest_right_bruteforce] can be greately improved if instead of looping from left to right, the scan is performed from right to left (from \(A.size()-2\) to \(0\))[^5]. This allows for keeping track of the maximum element on the right side of the element currenlty analyzed, \(M\), to be calculated in constant time because:

  • at first the maximum element on the right of \(A.size()-2\) is \(A.size()-1\) i.e. \(M = A[A.size()-1]\).

  • when \(A.size()-2\) is processed \(M\) can be updated by only using the the old value in \(A[A.size()-2]\) i.e. \(M= max(M, A_{old}[A.size()-2])\)

  • after each element \(i\) is processed: \(M= max(M, A_{old}[i+1])\)

The idea above is implemented in Listing [list:greatest_right_final1]

Listing 2: C++ linear time solution to the problem of modifying an array in place with the greatest element on the right side.

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

Please note how in Listing [list:greatest_right_final1]the variable \(m\) is used to keep track of the old value of the element of A currenlty processed and how the last element of \(A\) is always turned into \(-1\). An alternative and more condensed implementation is shown in Listing [list:greatest_right_final2].

Listing 3: Alternative Listing \ref{list:greatest_right_final1} implementation of C++ linear time solution to the problem of modifying an array in place with the greatest element on the right side.

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