Shuffle the Array

Difficulty: Easy | Acceptance: 88.90% | Paid: No Topics: Array

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

• Examples
• Constraints
• Two Pointers (New Array)
• In-place Encoding

Examples

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

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

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

Two Pointers (New Array)

Intuition Create a new array to store the result. Iterate through the first half of the input array, placing elements from the first half and the corresponding elements from the second half into the new array.

Steps

• Initialize a result array of size 2n.
• Loop from index 0 to n-1.
• Place the element from the first half (index i) at the even index (2*i) of the result array.
• Place the element from the second half (index i+n) at the odd index (2*i+1) of the result array.
• Return the result array.

from typing import List

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

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space proportional to the input size.

In-place Encoding

Intuition To achieve O(1) extra space, we can store two numbers at a single index using the fact that numbers are small (<= 10³). We use a base (e.g., 1024) to encode the pair (x, y) into a single value x + y * 1024.

Steps

• Iterate from 0 to n-1.
• Encode the pair (nums[i], nums[i+n]) at index i using the formula: nums[i] = nums[i] + (nums[i+n] % 1024) * 1024.
• Iterate from 0 to n-1 to decode and place them in correct positions.
• nums[2*i] = nums[i] % 1024 (retrieves x).
• nums[2*i + 1] = nums[i] / 1024 (retrieves y).
• Return the modified nums array.

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 + n] % 1024) * 1024
        
        for i in range(n):
            nums[2 * i] = nums[i] % 1024
            nums[2 * i + 1] = nums[i] // 1024
            
        return nums

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Modifies the input array in place. Relies on the constraint that nums[i] <= 10³.