Problem

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

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4

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

Example 3:

1
2
3
4

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

Solution

Method 1 – Interleaving with Two Pointers

Intuition

The problem is to rearrange the array by interleaving the first n and last n elements. We can do this by iterating through both halves and picking one from each alternately.

Approach

  1. Initialize an empty result array of size 2n.
  2. Use two pointers, one for the first half (x) and one for the second half (y).
  3. For each index from 0 to n-1, append nums[x] and nums[y] to the result.
  4. Return the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans(2*n);
        for (int i = 0; i < n; ++i) {
            ans[2*i] = nums[i];
            ans[2*i+1] = nums[i+n];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8

func shuffle(nums []int, n int) []int {
    ans := make([]int, 2*n)
    for i := 0; i < n; i++ {
        ans[2*i] = nums[i]
        ans[2*i+1] = nums[i+n]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] ans = new int[2*n];
        for (int i = 0; i < n; i++) {
            ans[2*i] = nums[i];
            ans[2*i+1] = nums[i+n];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun shuffle(nums: IntArray, n: Int): IntArray {
        val ans = IntArray(2*n)
        for (i in 0 until n) {
            ans[2*i] = nums[i]
            ans[2*i+1] = nums[i+n]
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def shuffle(self, nums: list[int], n: int) -> list[int]:
        ans = [0]*(2*n)
        for i in range(n):
            ans[2*i] = nums[i]
            ans[2*i+1] = nums[i+n]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn shuffle(nums: Vec<i32>, n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut ans = vec![0; 2*n];
        for i in 0..n {
            ans[2*i] = nums[i];
            ans[2*i+1] = nums[i+n];
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    shuffle(nums: number[], n: number): number[] {
        const ans = new Array(2*n);
        for (let i = 0; i < n; i++) {
            ans[2*i] = nums[i];
            ans[2*i+1] = nums[i+n];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we iterate through the array once.
  • 🧺 Space complexity: O(n), for the result array.