Shuffle the Array

How it works

Similar to the multiplication approach, we can use bit manipulation to pack two values into one integer. Since values fit in 10 bits (max 1000 < 1024 = 2^10), we can store one value in the lower 10 bits and another in the upper bits. First, we pack each x and its corresponding y into the first half of the array. Then we unpack them from back to front into their final interleaved positions, ensuring we do not overwrite values we still need.

Steps

1. For each i from 0 to n - 1:
   • Combine nums[i] (x) and nums[i + n] (y) into nums[i] using: nums[i] = (nums[i] << 10) | nums[i + n].
2. Starting from i = n - 1 down to 0, and using a pointer j starting at 2n - 1:
   • Extract y = nums[i] & ((1 << 10) - 1).
   • Extract x = nums[i] >> 10.
   • Place nums[j] = y and nums[j - 1] = x.
   • Decrement j by 2.
3. Return the modified array.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Using Wrong Index for the Y Values

The array is structured as [x1, x2, ..., xn, y1, y2, ..., yn], where the y values start at index n, not index n-1. A common mistake is using nums[n + i - 1] instead of nums[n + i] when pairing x[i] with its corresponding y value, resulting in incorrect pairings.

Overwriting Values in In-Place Solutions

When attempting an in-place shuffle without extra space, a frequent error is overwriting values before they have been used. The bit manipulation and multiplication/modulo approaches carefully encode two values in one element to avoid this, but implementing them incorrectly (such as reading from a position after it has already been modified) corrupts the data and produces wrong results.

from typing import List

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        for i in range(n):
            nums[i] = (nums[i] << 10) | nums[i + n]  # Store x, y in nums[i]

        j = 2 * n - 1
        for i in range(n - 1, -1, -1):
            y = nums[i] & ((1 << 10) - 1)
            x = nums[i] >> 10
            nums[j] = y
            nums[j - 1] = x
            j -= 2

        return nums

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        for (int i = 0; i < n; i++) {
            nums[i] = (nums[i] << 10) | nums[i + n]; // Store x, y in nums[i]
        }

        int j = 2 * n - 1;
        for (int i = n - 1; i >= 0; i--) {
            int y = nums[i] & ((1 << 10) - 1);
            int x = nums[i] >> 10;
            nums[j] = y;
            nums[j - 1] = x;
            j -= 2;
        }

        return nums;
    }
};