1
\$\begingroup\$

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:

  1. How can I further improve my approach?

  2. Is there a better way to solve this question?

  3. Are there any grave code violations that I have committed?

  4. Can space and time complexity be further improved?

Reference

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  • The recursion results in \$O(n)\$ space complexity (each recursive invocation consumes some stack), so technically you did not fulfill the requirement of _not using extra space. Since it is a tail recursion, it can easy to eliminate. Unfortunately, Java doesn't do it, so you have to eliminate it manually. Fortunately, it is just a mechanical rewrite.

  • The time complexity is \$O(n^2)\$. There is not much to do with the current approach. There is however a linear solution: an element at index k goes to either 2k, if k < n/2, or 2k - n + 1 otherwise. Convince yourself that this permutation has no loops, and just follow a chain of indices.

  • The loop

    for (int i = swapInd2 ; i > swapInd1; i--) {
        arr[i] = arr[i - 1];
    }
    

    shifts a range, and deserves to be a function on its own (shift_rangeperhaps).

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your suggestions. If I may ask, how is the space complexity O(n)? Do you refer to the continuous reallocation and shifting of the array? \$\endgroup\$ Sep 2, 2018 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.