Wave Array Given an array of integers, sort the array into a | Cse interview questions

Wave Array

Given an array of integers, sort the array into a wave like array and return it.

In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

NOTE : If there are multiple answers possible, return the one that is lexicographically smallest.

Examples :

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

Output 1 : [2, 1, 4, 3]

Explanation 1 :

Possible answers could be : [2, 1, 4, 3] or [4, 1, 3, 2]. We can see that integers at even index places (0-based) are greater than integers at their neighbouring odd index places.

Among these two, first one is preferred as it is lexicographically smallest.

Input 2 : [5, 20, 10]

Output 2 : [10, 5, 20]

Explanation 2 :

Possible answers could be : [10, 5, 20] or [20, 5, 10] among which first one is lexicographically smallest and so is selected as output.

Topic : Arrays

Reference -> InterviewBit

Solution -> GeeksforGeeks, AfterAcademy

Asked in Google, Adobe, Amazon

Join our Official Channel @cseinterview