Wave Array [MEDIUM]

Company: Paytm, Goldman-Sachs, Amazon

Question:

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.....

Example

Given [1, 2, 3, 4]

One possible answer : [2, 1, 4, 3]
Another possible answer : [4, 1, 3, 2]
 NOTE : If there are multiple answers possible, return the one thats lexicographically smallest. 

Input:

The first line contains an integer T, depicting total number of test cases. 
Then following T lines contains an integer N depicting the size of square matrix and next line followed by the value of array.

Output:

Print the array into wave like array.

Constraints:

1 ≤ T ≤ 30
1 ≤ N ≤ 100
0 ≤ A[i] ≤ 100

Example:

Input
1
5
5 7 3 2 8
Output
3 2 7 5 8

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

    Scanner sc = new Scanner (System.in);

    int m = sc.nextInt();

    for(int mi=0;mi<m;mi++){

        int n=sc.nextInt();

        int a []= new int [n];

        for(int size=0;size<n;size++){

            a[size]=sc.nextInt();

        }

        Arrays.sort(a);

        for(int i =0;i<n-1;i+=2){

            int temp=a[i];

            a[i]=a[i+1];

            a[i+1]=temp;

        }

        for(int j=0;j<n;j++){

            System.out.print(a[j]+" ");

        }

        System.out.println();

    }

}

}

EXECUTION TIME: 0.14s