Wave Array Problem

Difficulty: Easy, Asked-in: Google, Amazon, Adobe

Key takeaway: An excellent problem to learn problem-solving using sorting and single scan (Incrementing the loop by 2). Such problems are popular where we need to rearrange the input in place to get the output.

Let’s understand the problem

Given an unsorted array of n integers, write a program to sort the array into a wave array. An array A[n] is sorted in wave arrangement if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= …. Note: There can be multiple possible answers, but we need to return any one of the possible waveforms.

Example 1

Input: A[] = [1, 2, 3, 4]

Output: A[] = [2, 1, 4, 3] or [4, 1, 3, 2] or any other wave form like structure.

Example 2

Input: A[] = [20, 10, 8, 6, 4, 2]

Output: A[] = [20, 8, 10, 4, 6, 2] or [10, 8, 20, 2, 6, 4] or any other wave form like structure.

Discussed solution approaches

Brute force solution using sorting
Efficient solution using a single loop: Increment by 2

Brute force solution using sorting

Solution idea

If we look at the wave-like output, values are organized in an alternate order of large and small values. So how do we transform the given input in such an order? One idea is: If we sort the input array, can we arrange the elements in waveform? Let’s think!

In sorted array, all elements will be arranged in increasing order, i.e, A[0] ≤ A[1] ≤ A[2] ≤ A[3]≤ ….≤A[n - 2] ≤ A[n - 1]. So if we pick elements in pairs and swap the adjacent elements, the sorted array will get arranged in wave order. Think!

Visualization of sorted array

Visualization of the sorted array

Visualization after swapping adjacent elements in the sorted array

sort an array in a waveform solution idea

Solution code C++

// Function to convert the given array to wave form
void waveArray(int A[], int n)
{
    // sort the array
    sort(A, A + n);
    // swap adjacent elements
    for (int i = 0; i < n - 1; i = i + 2)
        swap(A[i], A[i + 1]);
}

Solution code Python

def waveArray(A):
    # sort the array
    A.sort()
    # swap adjacent elements
    for i in range(0, len(A) - 1, 2):
        A[i], A[i + 1] = A[i + 1], A[i]

Solution analysis

Suppose we use an O(nlogn) sorting algorithm like quicksort, merge sort, or heap sort. Time complexity = Time complexity of sorting + Time complexity of swapping adjacent elements = O(nlogn) + O(n) = O(nlogn)

Space complexity is O(1) if we use heap sort and O(n) if we use merge sort.

Efficient solution using a single loop: Increment by 2

Solution idea

The critical question is: Can we solve this problem in O(n) time complexity, i.e., without sorting? Let's think and explore one level further!

From the given output pattern, if we ensure that values at all the even positions are greater than the odd position, we can achieve the wave-like structure. In other words, for every even index i, we need to ensure this order in triplet (A[i - 1], A[i], A[i + 1]) => A[i - 1] < A[i] > A[i + 1].

There can be four possible cases for each triplet in the input array:

A[i - 1] < A[i] < A[i + 1]: We swap A[i] and A[i + 1] to get the order A[i - 1] < A[i] > A[i + 1].
A[i - 1] > A[i] > A[i + 1]: We swap A[i - 1] and A[i] to get the order A[i - 1] < A[i] > A[i + 1].
A[i - 1] > A[i] < A[i + 1]: We swap A[i - 1] and A[i] to get the order A[i - 1] < A[i]. Now if A[i] < A[i + 1], then we need to swap A[i] and A[i + 1].
A[i - 1] < A[i] > A[i + 1]: There is no need to do any swapping because values are already arranged in the required order.

If we observe, we can simplify further from cases 1, 2, and 3. The idea is simple: we need to place the max value of each triplet in the middle.

If A[i - 1] > A[i], swap A[i - 1] and A[i]
If A[i] < A[i + 1], swap A[i] and A[i + 1]

To implement this, we can run a loop incrementing by 2 to compare adjacent elements and ensure that all elements at even positions are greater than their adjacent elements at odd positions.

Solution steps

We run a loop incrementing by two to iterate over elements at even positions.
If current element A[i] is smaller than previous element A[i - 1], we swap current element A[i] with A[i - 1]. Note: We should avoid this operation for i = 0 because there is no previous element.
```
if(i > 0 && A[i - 1] > A[i])
   swap(A[i], A[i - 1])
```
If current element A[i] is smaller than next element A[i + 1], we swap current element A[i] with A[i + 1]. Note: We should avoid this operation for i = n - 1 because there is no next element.
```
if(i < n - 1 && A[i] < A[i + 1])  
   swap(A[i], A[i + 1])
```

Solution pseudocode

void waveArray(int A[], int n)
{ 
    for(int i = 0; i < n; i = i + 2)
    {
        if(i > 0 && A[i - 1] > A[i])
            swap(A[i], A[i - 1])
         
        if(i < n - 1 && A[i] < A[i + 1])  
            swap(A[i], A[i + 1])
    }
}

Implementation code C++

// Function to convert the given array to wave form
void waveArray(int A[], int n)
{
    // swap elements at even positions
    // with the element immediately following it
    // if it is greater
    for (int i = 0; i < n; i = 1 + 2)
    {
        if (i > 0 && A[i - 1] > A[i])
            swap(A[i], A[i - 1]);

        if (i < n - 1 && A[i] < A[i + 1])
            swap(A[i], A[i + 1]);
    }
}

Implementation code Python

def waveArray(A):
    # swap elements at even positions
    # with the element immediately following it
    # if it is greater
    for i in range(0, len(A), 2):
        if i > 0 and A[i - 1] > A[i]:
            A[i], A[i - 1] = A[i - 1], A[i]
        if i < len(A) - 1 and A[i] < A[i + 1]:
            A[i], A[i + 1] = A[i + 1], A[i]

Solution analysis

The time complexity for the above solution would be O(n) because we are linearly traversing the array and performing O(1) operations at each iteration. Space complexity = O(1) because we are using constant extra memory.

Critical ideas to think!

How do we modify the above solutions to output the lexicographically smallest solution?
How can we modify the above solution if adjacent elements are equal?
Can we solve this problem by picking elements at odd positions and comparing them with elements at even positions?
In the worst case, how many comparisons and swapping operations are made in the 2nd solution?
Can we solve this problem using another approach?
Can we think of solving this problem using recursion?
How many wave-like arrangements are possible for the given array of n distinct elements?
How can we modify the above solution when values at odd positions are greater than values at even positions?

Comparisons of time and space complexities

Using sorting: Time = O(nlogn), Space = O(1), if we use heap sort.
Using a single loop: Time = O(n), Space = O(1)

Sort an Array in a Waveform

Let’s understand the problem

Discussed solution approaches

Brute force solution using sorting

Solution idea

Solution code C++

Solution code Python

Solution analysis

Efficient solution using a single loop: Increment by 2

Solution idea

Solution steps

Solution pseudocode

Implementation code C++

Implementation code Python

Solution analysis

Critical ideas to think!

Comparisons of time and space complexities

Suggested coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs