AlgoMaster Logo

Shuffle the Array

easyFrequency5 min readUpdated June 23, 2026

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].

The element at index i in the first half pairs with the element at index n + i in the second half. That pair must end up adjacent in the result: nums[i] at position 2*i, and nums[n + i] at position 2*i + 1.

Key Constraints:

  • nums.length == 2n → The array always has an even number of elements, so there are no leftover or odd-length cases to handle.
  • 1 <= nums[i] <= 10^3 → Every value is positive and fits in fewer than 11 bits. Two such values fit comfortably in one 32-bit integer, which enables the O(1) space approach below.

Approach 1: New Array (Interleave)

Intuition

Create a separate result array and fill it by reading elements alternately from the two halves. For each index i from 0 to n - 1, write nums[i] (from the first half), then nums[n + i] (from the second half).

The index arithmetic follows from the pairing: 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. Because the result is a fresh array, the original values in nums are never disturbed while we read them.

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

Here n = 3, so the first half is [2, 5, 1] and the second half is [3, 4, 7]. We fill result one pair at a time:

  • i = 0: result[0] = nums[0] = 2, result[1] = nums[3] = 3 → [2, 3, _, _, _, _]
  • i = 1: result[2] = nums[1] = 5, result[3] = nums[4] = 4 → [2, 3, 5, 4, _, _]
  • i = 2: result[4] = nums[2] = 1, result[5] = nums[5] = 7 → [2, 3, 5, 4, 1, 7]

The final array is:

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

Code

The next approach removes the extra array and rearranges nums in place, using the small value range to store two numbers in one slot.

Approach 2: In-Place by Encoding Two Values

Intuition

The difficulty with rearranging in place is that writing the shuffled value into a slot would overwrite an original value that is still needed elsewhere. Since every value is at most 1000, we can sidestep this by storing two numbers in a single slot instead of choosing between them.

Pick a base maxVal = 1001, one larger than any value. A slot can then hold original + shuffled * maxVal: the original value is the remainder modulo maxVal, and the shuffled value is the quotient. The work happens in two passes. The first pass adds each shuffled value into its target slot, encoded as the high part. The second pass divides every slot by maxVal to keep only the shuffled value. No second array is allocated, so the extra space is O(1).

During encoding, a slot we read from may already hold an encoded pair, because each step writes to 2*i and 2*i + 1, which can be the same indices a later read touches. Taking % maxVal on every read recovers the original value regardless, so the order of the two writes does not affect correctness. Iterating from i = n - 1 down to 0 is one valid order.

Algorithm

  1. Set maxVal = 1001, one more than the largest possible value.
  2. First pass (encode): For each index i from n - 1 down to 0:
    • nums[2*i+1] += (nums[n + i] % maxVal) * maxVal places nums[n + i] as the high part of slot 2*i+1.
    • nums[2*i] += (nums[i] % maxVal) * maxVal places nums[i] as the high part of slot 2*i.
  3. Second pass (decode): For each index i from 0 to 2n - 1:
    • nums[i] = nums[i] / maxVal keeps only the high part, the shuffled 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