Problem Statement

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

Constraints:

• 1 <= n <= 500

• nums.length == 2n

• 1 <= nums[i] <= 10^3

Explanation

Here the array nums of size 2n is given
In example 1, the value of n is 3 so the size of nums array is 6
nums = [2,5,1,3,4,7], n = 3
The First Half of the array is denoted with x1, x2, and x3
x1 = 2
x2 = 5
x3 = 1

The second half of the array is denoted with y1, y2, and y3.
y1 = 3
y2 = 4
y3 = 7

We need to shuffle the array in such a way that the numbers appear in the sequence
[x1, y1, x2, y2, x3, y3]

At the end nums array should look like [2,3,5,4,1,7]

Solution

Let's see how we can solve this

• Brute Force Approach

Our array is something like this
nums - [2,5,1,3,4,7]
indices - 0 1 2 3 4 5

res - [2,3,5,4,1,7]
indices - 0 3 1 4 2 5

Here you can notice one thing, the first half of the nums are on even indices of res while the second half of the nums are on odd indices of res.

so how we can achieve it?

- first traverse the nums array from 0 to n-1
- to access the elements of the first half of the array we use nums[i] and for the second half of the array, we use nums[i+n]
- to store the elements on odd and even indices we use two variables
j -> for even indices
k -> for odd indices

Let's see the Dry Run of the code

int[] shuffle(int[] nums, int n) {
    int[] res = new int[2*n];
    for (int i=0, j=0, k=1; i < n-1; ++i, j+=2, k+=2) {
        res[j] = nums[i];
        res[k] = nums[i+n];
    }
    return res;
}

We can optimize the above solution
res - [2,3,5,4,1,7]
indices - 0 3 1 4 2 5

- Here second half of the array elements are adjacent to the first half of the array elements so we can replace 'k' with 'j+1'

Since we are iterating n times
Time Complexity - O(n)
and we have created a new array of size 2n
Space Complexity - O(n)

int[] shuffle(int[] nums, int n) {
    int[] res = new int[2*n];
    for (int i=0, j=0; i < n-1; ++i, j+=2) {
        res[j] = nums[i];
        res[j+1] = nums[i+n];
    }
    return res;
}

This solution is best for Time Complexity but if we want Space Complexity of O(1) then we can achieve it with another method

• O(1) Space Complexity Solution

Before moving forward let's make ourselves familiar with one concept
Do you remember,
Dividend = Divisor * Quotient + Remainder

We know,
60 = 15 * 4
60 can be completely divided with 15 and 4, if we divide 60 by 15 then we get 4 and if we divide 60 by 4 then we get 15
In 67 = 15 * 4 + 7, 67 can be divided by 15 and 4 and we get 7 as the remainder.

Now back to the question,
for O(1) Space Complexity, we will not use an additional array of size 2n as we did in the previous solution

---

LOGIC: We will create the pair of numbers which will be adjacent and store them in half of the array and will retrieve and store them one by one

---

For Example, if our array is [2,4,5,6,7,8] then we will store them as [(2,6), (4,7), (5,8)]
Why have we created pair of only these numbers?
We have created pair of (2,6), (4,7) and (5,8) because in the final array [2,6,4,7,5,8] they are adjacent to each other.

OK, we just need to store the pair and retrieve them, Simple. But how are we gonna do it Mathematically?

You will probably think that we can't store a pair of numbers like this in an array
YES, You are right we can't store them like this (2,6) but we can store them in a single number by using the concept we studied earlier.

for example, if we wanna store 2 and 6 then we will do it like this
2 * maxValue + 6.
Here maxValue should be greater than both the values 2 and 6
2 * 10 + 6 = 26 (maxValue = 10)
Now, if we divide 26 by 10 then we get 2 as the quotient and 6 as the remainder
Similarly, we can choose 7 as maxValue since it is greater than both 2 and 6
2 * 7 + 6 = 20

---

GENERAL FORMULA: num2 x maxValue + num1 = pairNumber
(Similar to, Dividend = Quotient x Divisor + Remainder)

---

Let's see how we can achieve it

• we will run two loops one to store the numbers (num1 and num2) as pairs and the second to retrieve them

• in the first loop, we will traverse it from n to 2n-1 because we will store the pairs in the right half of the array
  num1 will be elements from the left half of the array and num2 will be elements from right half of the array
  Example: In[2,4,5,6,7,8]
  num1 -> 2, 4 and 5
  num2 -> 6, 7 and 8
  As for the maxValue, we will take a value greater than 1000 because of the constraint 1 <= nums[i] <= 10^3 mentioned in the question

• now to retrieve the num1(Remainder) and num2(Quotient) we will do something like this
  num1 = pairNumber % maxValue;
  num2 = pairNumber / maxValue;

• To store these numbers adjacent to each other we will use 'j' as we use in the previous solution

public int[] shuffle(int[] nums, int n) {
        // to store the pair of numbers in right half of the original array
        for(int i = n; i < nums.length; i++) {
            nums[i] = (nums[i] * 1024) + nums[i - n];
        }

        // to retrive values from the pair of numbers 
        for(int i = n, j=0; i < nums.length; i++, j += 2) {
            nums[j] = nums[i] % 1024;
            nums[j + 1] = nums[i] / 1024;
        }

        return nums;
    }

As mentioned above we can use any number greater than 1000 for maxValue but we have used 1024 because we can make the solution faster by using bitwise operators so in that case we use 1024 to make the calculation easier but if you are not using bitwise operator we can take maxValue as 1001 or any number greater than 1000

Thanks for reading this blog, I Hope it helped you in understanding the question better.
If you want more solutions like this then subscribe to my newsletter, I am making a series of DSA-Days in which I will post one solution a day of leetcode question. The series will cover all types of questions like Easy/Medium/Hard and they will be topic-wise.