Wave Array in Java

(Asked in top MNC’S like AMAZON, MICROSOFT, GOLDMAN SACHS, PAYTM..etc)

Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

Problem Statement:

Given a sorted array arr[] of distinct 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….. (considering the increasing lexicographical order).

Input Format:
The first line contains an integer T, depicting total number of test cases. T testcases follow. The first line of each testcase contains an integer Ndepicting the size of the array. The second line contains N space separated elements of the array.

Output Format:
For each testcase, in a new line, print the array into wave-like array.

User Task:
The task is to complete the function convertToWave() which converts the given array to wave array. The newline is automatically added by the driver code.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10⁶
0 ≤ A[i] ≤10⁷

Example:
Input:
2
5
1 2 3 4 5
6
2 4 7 8 9 10

Output:
2 1 4 3 5
4 2 8 7 10 9

Explanation:
Testcase 1: Array elements after sorting it in wave form are 2 1 4 3 5.
Testcase 2: Array elements after sorting it in wave form are 4 2 8 7 10 9.

The simple apporach to solve the given problem is that

Iterate through the give array from index 0 to n-1 times by incrementing the value of i by 2.

Function to sort array in wave from given below:

public static void convertToWave(int arr[], int n){
        
      for(int i=0; i<n-1; i+=2) {
          int temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
         
      }
        
    }

the above apporach will take O(nLOGn) time for sorting algorithm like merge sort.

So i hope you all understand the simple implementation of wave array in java.

Thank You..

Happy Coding..!