Given an array of n elements in the following format { a1, a2, a3, a4, ….., an/2, b1, b2, b3, b4, …., bn/2 }. The task is shuffle the array to {a1, b1, a2, b2, a3, b3, ……, an/2, bn/2 } without using extra space.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow, Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array.
Output:
Print the shuffled array without using extra space.
Constraints:
1<=T<=10^5
1<=n<=10^5
1<=a[i]<=10^5
Example:
Input:
2
4
1 2 9 15
6
1 2 3 4 5 6
Output:
1 9 2 15
1 4 2 5 3 6
My approach:
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class ShuffleArray {
private static int [] getShuffledArray (int[] arr) {
//List <Integer> arrList = new ArrayList<>();
return shuffleArray(arr,1,arr.length/2);
}
private static int [] shuffleArray (int[] arr, int swapInd1, int swapInd2) {
if (swapInd2 == arr.length- 1) {
return arr;
}
int temp = arr[swapInd2];
for (int i = swapInd2 ; i > swapInd1; i--) {
arr[i] = arr[i - 1];
}
arr[swapInd1] = temp;
return shuffleArray(arr, swapInd1 + 2, swapInd2 + 1);
}
public static void main (String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int numTests = sc.nextInt();
while (numTests-- > 0) {
int size = sc.nextInt();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}
int[] soln = getShuffledArray(arr);
for (int i = 0; i < soln.length; i++) {
System.out.print(soln[i] + " ");
}
System.out.println();
}
}
}
}
I have the following questions with regards to the above code:
How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?