Scale Engineer

Shuffle the Array

Easy
#1357Time: 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: 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`.1 company
Data structures
Array
Companies
Zoho

Prompt

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

 

Example 1:

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:

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem