1.

You are given an array of integers. Your task is to Wave sort the array. For example, let us say the array is arr = {9,8,6,3,4,7,2}. Currently, the graph for the array of elements looks like this:

Answer»
We want the graph to look like this: It is not necessary that you print the same order of elements as shown above. You can print any other order but the shape of the graph of elements of the array should look like a wave. The graph should always start with the peak and not a valley. You are not allowed to use any extra space and you have to solve this problem in O(N) time complexity.

One basic approach to solve this problem is to sort the array and then swap the adjacent elements. The time complexity for which is O(NLog2N). Since we have to solve the problem in O(N) time complexity, we can solve it using the Wave Sort algorithm.

Our aim is to generate the Wave Graph. The aim can be accomplished by aiming at generating the peaks in the array or aiming at generating the valleys in the array. So, let us try to generate peaks in the array. Since we want the first array to be the peak, we will leave it as it is and start from the index = 2. Here, since we want to generate a peak, we need to have the previous and next elements smaller than our current elements. So, we will check that if our previous element is larger than our element, we will swap them. Again, at the same position, we will also check that the next element should be smaller than our current element. If it is not, swap these 2 elements. This is shown below.

So, we have to take a jump of 2 indices every time till we reach the end of the array. Hence, we will be able to wave sort the array in O(N) time and O(1) space.

Java Code for Wave Sort

import java.util.*;
class Main {

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void waveSort(int[] arr) {
for(int i=0;i<arr.length;i=i+2) {
if(i>0 && arr[i-1] > arr[i]) {
swap(arr,i-1,i);
}

if(i<arr.length-1 && arr[i+1] > arr[i]) {
swap(arr,i,i+1);
}
}
}

public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];

for(int i=0;i<n;i++) {
arr[i] = scn.nextInt();
}

waveSort(arr);

System.out.println("After wave sort");

for(int i=0;i<arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
}

Sample Output

Input:
7
9 8 6 3 4 7 2

Output:
After wave sort
9 6 8 3 7 2 4


  • Corner Cases, You Might Miss: Since we are swapping the previous element and the next element with the current element, we have to take care of the Index out of bounds condition. This is done in the code above.


  • Time Complexity: O(N) as we are traversing the array.


  • Auxiliary Space: O(1) as we have not used any extra space.


Discussion

No Comment Found

Related InterviewSolutions