Shuffle the Array

EASY

Description

Given the array nums consisting of 2n elements in the form [x₁,x₂,...,x_n,y₁,y₂,...,y_n].

Return the array in the form [x₁,y₁,x₂,y₂,...,x_n,y_n].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x₁=2, x₂=5, x₃=1, y₁=3, y₂=4, y₃=7 then the answer is [2,3,5,4,1,7].

Example 2:

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

Example 3:

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

Approaches

Checkout 2 different approaches to solve Shuffle the Array. Click on different approaches to view the approach and algorithm in detail.

Using an Extra Array

This approach involves creating a new array of the same size (2n) and filling it with elements from the input array in the desired shuffled order. It's the most straightforward and intuitive way to solve the problem.

Algorithm

Create a new integer array result of size 2n.
Iterate with an index i from 0 to n-1.
For each i, place nums[i] (which is x_i) at result[2*i].
Place nums[i+n] (which is y_i) at result[2*i + 1].
Return the result array.

The algorithm directly constructs the shuffled array by allocating new memory. It iterates through the first half of the input array (the x elements) and, for each x_i, it picks both x_i and its corresponding y_i and places them sequentially into the new result array.

For example, for i=0, it takes nums[0] (x₁) and nums[n] (y₁) and places them at result[0] and result[1]. For i=1, it takes nums[1] (x₂) and nums[n+1] (y₂) and places them at result[2] and result[3], and so on.

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[2 * n];
        for (int i = 0; i < n; i++) {
            result[2 * i] = nums[i];
            result[2 * i + 1] = nums[i + n];
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) - We iterate through the first half of the array once, performing constant time operations inside the loop. The total number of operations is proportional to `n`.Space Complexity: O(n) or O(2n) - We create a new array of size `2n` to store the shuffled elements. The space required is proportional to `n`.

Pros and Cons

Pros:

Simple and easy to understand.
The code is clean and readable.
Not dependent on the constraints of the values in the array.

Cons:

Requires extra space proportional to the input size, which can be inefficient for very large arrays.

Code Solutions

Checking out 3 solutions in different languages for Shuffle the Array. Click on different languages to view the code.

class Solution { public int [] shuffle ( int [] nums , int n ) { int [] ans = new int [ n << 1 ]; for ( int i = 0 , j = 0 ; i < n ; ++ i ) { ans [ j ++] = nums [ i ]; ans [ j ++] = nums [ i + n ]; } return ans ; } }

Video Solution

Watch the video walkthrough for Shuffle the Array

Data Structures:

Array

Companies:

Zoho |