1470. Shuffle the Array - Explanation

1. Iteration (Extra Space)

Intuition

The array is given as [x1, x2, ..., xn, y1, y2, ..., yn] and we need to rearrange it to [x1, y1, x2, y2, ..., xn, yn]. The simplest approach is to iterate through the first half of the array and alternate between picking elements from the first half (x values at index i) and the second half (y values at index i + n). We build the result in a new array.

Algorithm

Create an empty result array.
Loop i from 0 to n - 1:
- Append nums[i] (the x value) to the result.
- Append nums[i + n] (the corresponding y value) to the result.
Return the result array.

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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ extra space.

2. Multiplication And Modulo

Intuition

To shuffle in-place without extra space, we can encode two values in a single array element. Since values are at most 1000, we pick a base M > 1000. For each position i in the result, we determine which original element belongs there and encode it by adding original_value * M to nums[i]. The original value is retrieved using nums[index] % M (since we have not yet divided), and the new value is stored in the upper part. After encoding all positions, we divide each element by M to extract the shuffled values.

Algorithm

Choose M = max(nums) + 1 or a constant like 1001.
For each index i from 0 to 2n - 1:
- If i is even, the value should come from position i / 2 (an x value).
- If i is odd, the value should come from position n + i / 2 (a y value).
- Add (nums[source] % M) * M to nums[i].
Divide each element by M to get the final shuffled array.
Return the modified array.

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        M = max(nums) + 1
        for i in range(2 * n):
            if i % 2 == 0:
                nums[i] += (nums[i // 2] % M) * M
            else:
                nums[i] += (nums[n + i // 2] % M) * M

        for i in range(2 * n):
            nums[i] //= M

        return nums

Time & Space Complexity

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

3. Bit Manipulation

Intuition

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.

Algorithm

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].
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.
Return the modified array.

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

Time & Space Complexity

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

Common Pitfalls

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.