# Shuffle the Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/shuffle-the-array)
Canonical: https://scaleengineer.com/dsa/problems/shuffle-the-array
**Data structures:** Array
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
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]

**Example 3:**

**Input:** nums = [1,1,2,2], n = 2
**Output:** [1,2,1,2]

**Constraints:**

* `1 <= n <= 500`
* `nums.length == 2n`
* `1 <= nums[i] <= 10^3`

# Approaches
## Using an Extra Array
This approach involves creating a new array of the same size (`2n`) and filling it with elements from the input array in the desired shuffled order. It's the most straightforward and intuitive way to solve the problem.
**Time:** O(n) - We iterate through the first half of the array once, performing constant time operations inside the loop. The total number of operations is proportional to `n`. · **Space:** O(n) or O(2n) - We create a new array of size `2n` to store the shuffled elements. The space required is proportional to `n`.
**Pros:** Simple and easy to understand.; The code is clean and readable.; Not dependent on the constraints of the values in the array.
**Cons:** Requires extra space proportional to the input size, which can be inefficient for very large arrays.
### Explanation
The algorithm directly constructs the shuffled array by allocating new memory. It iterates through the first half of the input array (the `x` elements) and, for each `x_i`, it picks both `x_i` and its corresponding `y_i` and places them sequentially into the new result array. 

For example, for `i=0`, it takes `nums[0]` (x₁) and `nums[n]` (y₁) and places them at `result[0]` and `result[1]`. For `i=1`, it takes `nums[1]` (x₂) and `nums[n+1]` (y₂) and places them at `result[2]` and `result[3]`, and so on.

```java
class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[2 * n];
        for (int i = 0; i < n; i++) {
            result[2 * i] = nums[i];
            result[2 * i + 1] = nums[i + n];
        }
        return result;
    }
}
```
### Algorithm
*   Create a new integer array `result` of size `2n`.
*   Iterate with an index `i` from `0` to `n-1`.
*   For each `i`, place `nums[i]` (which is `x_i`) at `result[2*i]`.
*   Place `nums[i+n]` (which is `y_i`) at `result[2*i + 1]`.
*   Return the `result` array.

## In-place Shuffle using Bit Manipulation
This approach modifies the input array directly without using significant extra space. It leverages the constraint that the numbers are small (`<= 1000`) to store two numbers in a single integer slot. By encoding both the original and the new value at a location, we can perform the shuffle in-place.
**Time:** O(n) - The encoding phase involves a loop that runs `n` times. The decoding phase involves a loop that runs `2n` times. Both loops perform constant time bitwise operations. The total time complexity is O(n) + O(2n), which simplifies to O(n). · **Space:** O(1) - The shuffle is performed in-place on the input array. No auxiliary data structures proportional to the input size are used.
**Pros:** Extremely space-efficient, using O(1) extra space.; Maintains a linear time complexity.
**Cons:** The logic is significantly more complex and less intuitive than the extra array approach.; This solution is highly dependent on the constraints of the input values (i.e., they must be small enough to allow for encoding).; The code is less readable and harder to maintain.
### Explanation
The core idea is to use the 32 bits of an integer to store two numbers. Since `nums[i] <= 1000`, each number can be represented by 10 bits (as `2^10 = 1024`). We can use the lower 10 bits for the original value at a location and the next 10 bits for the new value that should be at that location.

The process involves two main passes over the array:
1.  **Encoding:** In the first pass, we iterate through the array and for each position, we calculate what the new value should be. We then store this new value in the higher-order bits of that same array element, without disturbing the original value in the lower-order bits. When fetching a value that will become a 'new value', we must mask it to ensure we're using its original value, in case it has already been encoded.
2.  **Decoding:** In the second pass, we iterate through the array again. This time, we simply right-shift each element's bits to discard the old value and keep only the new, final value.

```java
class Solution {
    public int[] shuffle(int[] nums, int n) {
        // Constraint: 1 <= nums[i] <= 1000. 10 bits are enough (2^10 = 1024).
        // We store the new value in the higher 10 bits and keep the old value in the lower 10 bits.

        // 1. Encoding phase
        for (int i = 0; i < n; i++) {
            // Get original values by masking, in case they were already encoded.
            int x_i = nums[i] & 1023;
            int y_i = nums[i + n] & 1023;

            // Encode the new values into their final positions.
            // Final position for x_i is 2*i
            // Final position for y_i is 2*i+1
            nums[2 * i] |= (x_i << 10);
            nums[2 * i + 1] |= (y_i << 10);
        }

        // 2. Decoding phase
        for (int i = 0; i < 2 * n; i++) {
            nums[i] = nums[i] >> 10;
        }

        return nums;
    }
}
```
### Algorithm
*   The approach uses bit manipulation to store two numbers in a single array slot, enabling an in-place shuffle.
*   It consists of an encoding phase and a decoding phase.
*   **Encoding Phase:**
    *   Iterate from `k = 0` to `n-1`.
    *   For each `k`, we determine the two values that need to be placed: `x_{k+1}` (from `nums[k]`) and `y_{k+1}` (from `nums[n+k]`).
    *   The destination for `x_{k+1}` is `nums[2*k]` and for `y_{k+1}` is `nums[2*k+1]`.
    *   We store the new value in the higher bits of the destination slot, while preserving the old value in the lower bits. The formula is `nums[dest] |= (new_value << 10)`.
    *   Crucially, when we retrieve a `new_value` (e.g., `nums[k]`), we must mask it (`nums[k] & 1023`) to get its original value, as it might have been encoded in a previous step.
    *   So, `nums[2*k] |= (nums[k] & 1023) << 10`.
    *   And `nums[2*k+1] |= (nums[n+k] & 1023) << 10`.
*   **Decoding Phase:**
    *   After encoding all values, iterate through the entire array from `i = 0` to `2n-1`.
    *   Right-shift each element by 10 bits to retrieve the stored new value: `nums[i] = nums[i] >> 10`.
    *   The array is now shuffled in-place.

# Solutions
### Java

```java
class Solution { public int [] shuffle ( int [] nums , int n ) { int [] ans = new int [ n << 1 ]; for ( int i = 0 , j = 0 ; i < n ; ++ i ) { ans [ j ++] = nums [ i ]; ans [ j ++] = nums [ i + n ]; } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > shuffle ( vector < int >& nums , int n ) { vector < int > ans ; for ( int i = 0 ; i < n ; ++ i ) { ans . push_back ( nums [ i ]); ans . push_back ( nums [ i + n ]); } return ans ; } };
```

### Python

```python
class Solution : def shuffle ( self , nums : List [ int ], n : int ) -> List [ int ]: ans = [] for i in range ( n ): ans . append ( nums [ i ]) ans . append ( nums [ i + n ]) return ans
```