AlgoMaster Logo

Shuffle the Array

Last Updated: March 31, 2026

easy

Understanding the Problem

The array is split into two halves of size n. The first half holds [x1, x2, ..., xn] and the second half holds [y1, y2, ..., yn]. We need to interleave them so the result alternates between elements from the first half and the second half: [x1, y1, x2, y2, ..., xn, yn].

Think of it like shuffling a deck of cards. You split the deck into two halves and then weave them together, alternating one card from each half. The key observation is that the element at index i in the first half pairs with the element at index n + i in the second half. Once you see this pairing, the solution becomes straightforward.

Key Constraints:

  • 1 <= n <= 500 → The array length is at most 1000. Even an O(n^2) solution would only do 1,000,000 operations, which is well within time limits. O(n) is easy to achieve and preferred.
  • nums.length == 2n → The array always has an even number of elements. No need to handle odd-length arrays or leftover elements.
  • 1 <= nums[i] <= 10^3 → All values are positive integers that fit in 10 bits. This is relevant for the bit manipulation approach that achieves O(1) space.

Approach 1: New Array (Interleave)

Intuition

The most natural way to think about this: create a new result array and fill it by picking elements alternately from the two halves. For each index i from 0 to n-1, we place nums[i] (from the first half) followed by nums[n + i] (from the second half) into the result.

This directly mirrors the problem description. The pairing is clear: position i in the first half maps to position 2*i in the result, and position n + i in the second half maps to position 2*i + 1 in the result.

Algorithm

  1. Create a new array result of size 2n.
  2. For each index i from 0 to n - 1:
    • Place nums[i] at result[2 * i].
    • Place nums[n + i] at result[2 * i + 1].
  3. Return result.

Example Walkthrough

Input:

0
2
1
5
2
1
3
3
4
4
5
7
nums

After interleaving (place nums[i] at result[2i], nums[n+i] at result[2i+1]):

0
2
1
3
2
5
3
4
4
1
5
7
result

Code

This approach works correctly but uses extra space. Since values are at most 1000 (fitting in 10 bits), what if we encoded both the original and new values into the same array position?

Approach 2: In-Place with Bit Manipulation

Intuition

Since each value in nums is at most 1000, it fits in 10 bits. An integer has 32 bits, which means we can store two values in a single position. We pack the new value into the upper bits while keeping the original value in the lower bits.

The idea works in two passes. In the first pass, we encode each position to hold both its original value and the value it should have in the final result. In the second pass, we extract just the new values. This gives us O(1) extra space since we modify the array in place.

The trick is to work backwards from index n - 1 to 0 during the encoding phase. Going backward ensures we always read original values (or values we can recover with % maxVal).

Algorithm

  1. Store the maximum possible value plus 1 as maxVal = 1001 (since values go up to 1000).
  2. First pass (encode): For each index i from n - 1 down to 0:
    • At position 2 * i + 1, encode: nums[2*i+1] += (nums[n + i] % maxVal) * maxVal
    • At position 2 * i, encode: nums[2*i] += (nums[i] % maxVal) * maxVal
  3. Second pass (decode): For each index i from 0 to 2n - 1:
    • nums[i] = nums[i] / maxVal to extract the encoded new value.

Example Walkthrough

1Initialize: encode right to left, starting at i=2
0
2
1
5
2
i=2
1
3
3
4
4
2*i
5
7
2*i+1
1/6

Code