Coding interview Essentials

9. Wave Array

Wave Array

Introduction

We are used to talking about sorting in terms of arranging items in either ascending or descending order. But in general, sorting is the process of arranging items systematically, according to a criterion that can be purely arbitrary.

The problem discussed in this lesson is about writing an algorithm for sorting the items of a collection in a rather unusual and peculiar way: the goal is to place elements at even indices such that they all are surrounded by either greater or smaller elements. For instance, the collection: \(\{1,3,-1,3,2,4\}\) is properly sorted while \(\{1,3,-1,1,2,4\}\) is not.

This question has been asked at companies like Adobe, and Google, mostly during the firsts on-site interview stages as it is not considered to be a very hard one and it can be solved by writing just a handful of lines. In fact, if the candidate comes up with the right idea and makes no implementation mistakes, this problem can be cleared rather quickly. However, this problem has proven to be challenging for many, especially in getting it right the first time: once a working draft of the solution is finished, our advise is to spend some time to make sure the code is behaving as expected, especially on corner cases.

Problem statement

[ex:wave_array:statement]

Given an array \(A\) of \(n\) integers, arrange the numbers in a wave-like fashion. A valid wave array \(X\) has its elements arranged in one of the two following ways:

  1. \(x_0 \geq x_1 \leq x_2 \geq x_3 \leq x_5 \geq \ldots\) where \(x_{2i-1} \geq x_{2i} \leq x_{2i+1}\)

  2. \(x_1 \leq x_2 \geq x_3 \leq x_4 \geq x_5 \leq \ldots\) where \(x_{2i-1} \leq x_{2i} \geq x_{2i+1}\)


[ex:wave_array:example1] Given \(A= \{10, 5, 6, 3, 2, 20, 100, 80\}\) the followings are all valid output (see Figure 9.1):

  • {20, 5, 10, 2, 80, 6, 100, 3}

  • {10, 5, 6, 2, 20, 3, 100, 80}


[ex:wave_array:example2] Given \(A= \{20, 10, 8, 6, 4, 2\}\) the followings are all valid output (see Figure 9.1):

  • {20, 8, 10, 4, 6, 2}

  • {10, 8, 20, 2, 6, 4}


[ex:wave_array:example3] Given \(A= \{10,9,8,7,6,5,4,3,2,1\}\) the following is a output: \(\{10, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1 \}\) (see Figure 9.1).

Figure 1: Input and solutions for Example [ex:wave_array:example1].
Figure 2: Input and solutions for Example [ex:wave_array:example2].
Figure 3: Input and solutions for Example [ex:wave_array:example3].

Clarification Questions

Does the array \(A\) only contain positive numbers?

No, the input numbers can be positive or negative.

Are duplicates in \(A\) allowed?

Yes, duplicates might be present.

Do the numbers in \(A\) lie in a given particular range? If yes which one?

No; no assumptions can be made on the values in \(A\).

Discussion

The challenge confronting us is about the creation of an entirely new array \(X\) (we, therefore, know from the very beginning we must make a copy of \(A\) at some point) that contains the same elements in \(A\), arranged in a form that reminds a wave. An array of this type has its elements arranged so that they produce a zig-zig-like pattern when plotted on a graph.

Sequences of numbers of this type can be described as having the property that all of their elements located at even indices are all either local minima or maxima[^6]. Identifying a local minimum/maximum is easy but, it is only helpful when we want to test whether a sequence is a valid wave array.

Brute-force

One way to attack this problem is by enumerating every possible arrangement of the elements of \(A\) and apply the criteria of wave-array validity discussed above to find a solution. We can enumerate all permutations of an array quite easily by using a function like which (taken from the docs):

This idea is implemented in Listing [list:wave_array_linear_bruteforce].

Listing 1: Brute-force time solution to the wave array problem.

template<typename It, typename Cmp_fn>
bool is_valid_wave_array(It begin, It end, Cmp_fn fn = std::greater<int>())
{
  It curr = begin;
  while(curr != end){
    
    if(const It prev = curr-1; prev >= begin && !cmp_fn(curr, prev))
      return false;
    
    if(const It next = curr+1; next < end && !cmp_fn(curr, next))
      return false;
  }
  return true;
}

std::vector<int> wave_brute_force(const std::vector<int> &A)
{
  std::vector<int> B(A);
  std::sort(begin(B), end(B));
  
  do {
    if(is_valid_wave_array(B.begin(), B.end(), std::greater<int>()) || 
      is_valid_wave_array(B.begin(), B.end(), std::less<int>()) )
      return B;
  } while ( std::next_permutation(B.begin(),B.end()) );
  
  throw std::runtime_error("Should never happen");
}

The code above has a time complexity that is proportional to \(n!\) and it is, therefore, impractical to use even for smaller sized arrays as the factorial of \(10\) is already greater than \(3\) million.

Sorting

As per all array problems, the first question that should come to mind is: does sorting the elements (we are referring here to a canonical sorting in increasing order) change the difficulty of the problem? Incrementally sorted sequences are easy to reason about, as they provide strong and clear guarantees on how elements relate to each other. Most importantly, the same problem is very often a lot easier to solve on a sorted collection than on an unsorted one.

If we apply the wave-array validity criterion (discussed above on local minima/maxima) on a sorted array \(S=\{s_0 \leq s_1 \leq \ldots \leq s_{n-1}\}\) we notice that \(S\) fails the test as there is only one local minimum and local maximum i.e. \(s_0\) and \(s_{n-1}\) (which also happen to be the global minimum and maximum).

But how does \(S\) change if every element that is located at an even index is swapped with its subsequent neighbor? When every elements at indices \(2i\) and \(2i+1\) (\(i=0,1,\ldots\)) are swapped, then: \(S=\{s_1 \geq s_0 \leq s_3 \geq s_2 \leq s_5 \geq s_4 \leq s_7 \geq \ldots\}\) which is now in better shape to pass the wave-array validity test as now every element at even index is surrounded by smaller (or equal) elements.

Notice that the elements of \(S\) have been shuffled around, and that now the element \(a_i\) is not located at index \(i\) anymore (contrary to how it was originally). We can see that \(a_3\) is now located at index \(2\) and it is surrounded by \(a_0\) and \(a_2\), which are both smaller or equal to \(a_3\). Similarly, \(a_5\) is now placed at index \(4\) and it is surrounded by the elements \(a_2\) and \(a_4\), both known to be smaller or equal than \(a_5\).

We can use this observation to solve this problem efficiently and elegantly as shown in Listing [list:wave_array_sorting].

Listing 2: Solution to the wave array problem using sorting.

std::vector<int> wave_sorting(const std::vector<int> &A)
{
  std::vector<int> B(A);
  std::sort(begin(B), end(B));
  auto it = B.begin();
  for (auto it = B.begin(); it + 1 < B.end(); it += 2)
  {
    std::swap(*it, *(it + 1));
  }
  return B;
}

Solution [list:wave_array_sorting] works by creating a copy of the input array \(A\) named \(B\), which is subsequently sorted. The code then proceeds in swapping every element located at an even location with the element after it. You can see the operation is applied to the iterators and , and that at the end of each iteration is incremented by \(2\). This, together with the fact initially pointer to the first even element at location \(0\), effectively means that only pairs of items at indices of the form \((2i, 2i+1)\) are swapped.

This solution is considered to be a good one, as its time and space complexity are both \(O(nlog(n))\) and \(O(n)\), respectively.

In some cases, the interviewer might ask to return, among all possible valid arrangements, the one being the lexicographically minimum. If it is the case, the solution proposed below won’t work and it should not be attempted.

Linear time solution

Despite the solution using sorting presented in Section 9.3.2 is already good enough to possibly clear the interview, there exists a solution that works in linear time and that is as easy to implement and explain. The core idea is always the same: elements at even index should always be greater (or smaller, equivalently) than their adjacents neighbors. Only this time we will enforce it in a single pass on the array, by swapping elements at even indices with their direct neighbors (to the left and to the right) if they happen to be smaller in such a way that the largest element among \(x_{2i-1},x_{2i},x_{2i+1}\) always ends up going to the location \(2i\).

We can do that by iterating over all even indices and performing the following operations:

  1. if the current element \(a_{2i}\) is smaller than the element \(a_{2i-1}\) then swap them;

  2. if the current element \(a_{2i}\) (possibly newly assigned from the previous step) is smaller than the element \(a_{2i+1}\) then swap them.

At this point we have effectively placed the largest among \(x_{2i-1},x_{2i},x_{2i+1}\) at the location \(2i\) and we can proceed to the next even element \(a_{2(i+1)}\).

See Listing [list:wave_array_linear] for a possible implementation of this idea.

Listing 3: Linear time solution to the wave array problem.

std::vector<int> wave_linear(const std::vector<int> &A)
{
  if (A.size() <= 2)
    return A;

  std::vector<int> B(A);
  for (size_t i = 0; i < B.size(); i += 2)
  {
    if (i > 0 && B[i - 1] > B[i])
      std::swap(B[i - 1], B[i]);

    if (i < B.size() - 1 && B[i + 1] > B[i])
      std::swap(B[i + 1], B[i]);
  }
  return B;
}

Notice that the code above performs some checks on the corner elements so that we do not perform out-of-bound accesses. This solution is optimal as it runs in \(o(n)\) space and time.

Like the solution using sorting, it does not work when the lexicographical minimum arrangement should be returned.

Common Variations - Return the lexicographically smallest

One of the most common variations of this problem is the one where you are required to return the lexicographically minimum wave-like arrangement of \(A\). In this exercise, you have the chance to apply everything we have learned about this problem so far and write an efficient solution for this variation.

Problem statement

Given an array \(A\) of \(n\) integers, arrange the numbers in a wave-like fashion (see Section [ex:wave_array:statement] for a definition of wave-array). If there are multiple valid answers, the function returns the one that is lexicographically smallest.

  1. \(x_0 \geq x_1 \leq x_2 \geq x_3 \leq x_5 \geq \ldots\) where \(x_{2i-1} \geq x_{2i} \leq x_{2i+1}\)

  2. \(x_1 \leq x_2 \geq x_3 \leq x_4 \geq x_5 \leq \ldots\) where \(x_{2i-1} \leq x_{2i} \geq x_{2i+1}\)


[ex:wave_array:var1:example1] Given \(A=\{1, 2, 3, 4\}\) the function returns {2, 1, 4, 3}. Notice that the sequence {4, 1, 3, 2} is also a valid wave-array but it is not lexicographically minimal.