Wave Array

Difficulty: Easy

Asked in: Amazon, Google, Adobe

You are given an unsorted array of integers( arr ) of length n , write a program to sort it in wave form.

Problem Note:

The array elements in the resultant array must be such that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] .....
If there are multiple sorted orders in wave form, return the one which is lexicographically smallest.
The array may contain duplicates.

Example 1

Input: arr = [5, 2, 9, 3, 2]
Output: [2, 2, 5, 3, 9]
Explanation: In the above example, you can see 2 >= 2 <= 5 >= 3 <= 9. Thus we get, arr = [2, 2, 5, 3, 9] as output which is sorted in wave form.

Example 2

Input: arr = [3, 2, 9, 6, 4, 1]
Output: [2, 1, 4, 3, 9, 6]
Explanation: In the above example, you can see 2 >= 1 <= 4 >= 3 <= 9 >= 6. Thus we get, arr = [2, 1, 4, 3, 9, 6] as output which is sorted in wave form.

Example 3

Input: arr = [4, 2, 9, 1, 21, 43, 24]
Output: [2, 1, 9, 4, 24, 21, 43]
Explanation: In the above example, you can see 2 >= 1 <= 9 >= 4 <= 24 >= 21 <= 43. Thus we get, arr = [2, 1, 9, 4, 24, 21, 43] as output which is sorted in wave form.

Solutions

For this problem, we will be discussing two possible solutions:-

Sorting and swapping: Sort the array and swap the adjacent values.
Comparing neighbours: Compare neighbouring elements and swap if the problem condition doesn’t satisfy.

You can try the problem here.

1. Sorting and Swapping

The problem asks that the array elements in the resultant array must be such that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] ..... . So, one can find many different solutions for one input. However, the problem statement also requires to return the lexicographically smallest array. So, We can generalize the outputs in a simple way.

We can directly sort the input array so that arr[0] <= arr[1] <= arr[2] <= arr[3] <= arr[4] ..... now, swapping the alternate elements i.e. arr[0] with arr[1] and arr[2] with arr[3] and arr[4] with arr[5] and …, we will have the resultant array satisfying the problem condition.

Solutions steps

Sort the array in ascending order.
Swap the adjacent elements.

Pseudo Code

int[] waveArray(int arr[], int n) { 
    // Sort the input array 
    arr.sort()
  
    // Swap adjacent elements 
    i = 0
    while(i < n-1){
        swap(arr[i], arr[i+1])
        i = i + 2
    }
    return arr
}

Complexity Analysis

Time Complexity: O(n log n) (How?)

Space Complexity: O(1)

Critical Ideas To Think

Can we solve this problem by sorting the array in decreasing order and then swapping adjacent values?
The problem requires the array to satisfy just the relationship between the neighbouring elements, so is sorting even required?
Is the solution is lexicographically smallest answer? Answer: Yes
Try to optimize the running time complexity.

2. Comparing Neighbors

We can optimize the previous approach as we can only focus on maintaining the condition for neighbouring elements. However, this will not guarantee the lexicographically smallest array in return.

If we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd positioned elements, we won’t have to check the oddly positioned element.

Solution Steps

Traverse all even positioned elements of the input array, and do the following — >

If the current element is smaller than the previous odd element, swap previous and current.
If the current element is smaller than the next odd element, swap next and current.

Pseudo Code

int[] waveArray(int arr[], int n) { 
    i = 0
    while (i < n) { 
        // If current even index element is smaller than previous 
        if (i > 0 and arr[i-1] > arr[i] ) 
            swap(arr[i], arr[i-1])
        // If current even index element is smaller than next 
        if (i < n-1 and arr[i] < arr[i+1] ) 
            swap(arr[i], arr[i + 1])
        i = i + 2
    } 
    return arr
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think

Does the solution return the lexicographically smallest array? If No, Why?
Do you think any solution is possible which guarantees lexicographically smallest array with linear run-time complexity?
How did we make sure that only comparing the neighbouring elements and swapping elements as per the required condition will satisfy the problem condition?
If the input array is already sorted, then the output array according to this approach will be a lexicographically smallest array. True or False?
Looking at the pseudo-code, what are the previous and next elements for each current element?