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 < n1){
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[i1] > arr[i] )
swap(arr[i], arr[i1])
// If current even index element is smaller than next
if (i < n1 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 runtime 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 pseudocode, what are the previous and next elements for each current element?
Comparison of Different Solutions
Suggested Problems To Solve
 Check if an array is a wave array
 Find if an integer p exists in the array such that the number of integers greater than p in the array equals to p .
 Sort array with squares
 Sort array of 0s, 1s, and 2s.
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding!
Enjoy Algorithms!