Shuffle the Array
EasyPrompt
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 <= 500nums.length == 2n1 <= 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
resultof size2n. - Iterate with an index
ifrom0ton-1. - For each
i, placenums[i](which isx_i) atresult[2*i]. - Place
nums[i+n](which isy_i) atresult[2*i + 1]. - Return the
resultarray.
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.
This approach modifies the input array directly without using significant extra space. It leverages the constraint that the numbers are small (<= 1000) to store two numbers in a single integer slot. By encoding both the original and the new value at a location, we can perform the shuffle in-place.
Algorithm
- The approach uses bit manipulation to store two numbers in a single array slot, enabling an in-place shuffle.
- It consists of an encoding phase and a decoding phase.
- Encoding Phase:
- Iterate from
k = 0ton-1. - For each
k, we determine the two values that need to be placed:x_{k+1}(fromnums[k]) andy_{k+1}(fromnums[n+k]). - The destination for
x_{k+1}isnums[2*k]and fory_{k+1}isnums[2*k+1]. - We store the new value in the higher bits of the destination slot, while preserving the old value in the lower bits. The formula is
nums[dest] |= (new_value << 10). - Crucially, when we retrieve a
new_value(e.g.,nums[k]), we must mask it (nums[k] & 1023) to get its original value, as it might have been encoded in a previous step. - So,
nums[2*k] |= (nums[k] & 1023) << 10. - And
nums[2*k+1] |= (nums[n+k] & 1023) << 10.
- Iterate from
- Decoding Phase:
- After encoding all values, iterate through the entire array from
i = 0to2n-1. - Right-shift each element by 10 bits to retrieve the stored new value:
nums[i] = nums[i] >> 10. - The array is now shuffled in-place.
- After encoding all values, iterate through the entire array from
Walkthrough
The core idea is to use the 32 bits of an integer to store two numbers. Since nums[i] <= 1000, each number can be represented by 10 bits (as 2^10 = 1024). We can use the lower 10 bits for the original value at a location and the next 10 bits for the new value that should be at that location.
The process involves two main passes over the array:
- Encoding: In the first pass, we iterate through the array and for each position, we calculate what the new value should be. We then store this new value in the higher-order bits of that same array element, without disturbing the original value in the lower-order bits. When fetching a value that will become a 'new value', we must mask it to ensure we're using its original value, in case it has already been encoded.
- Decoding: In the second pass, we iterate through the array again. This time, we simply right-shift each element's bits to discard the old value and keep only the new, final value.
class Solution { public int[] shuffle(int[] nums, int n) { // Constraint: 1 <= nums[i] <= 1000. 10 bits are enough (2^10 = 1024). // We store the new value in the higher 10 bits and keep the old value in the lower 10 bits. // 1. Encoding phase for (int i = 0; i < n; i++) { // Get original values by masking, in case they were already encoded. int x_i = nums[i] & 1023; int y_i = nums[i + n] & 1023; // Encode the new values into their final positions. // Final position for x_i is 2*i // Final position for y_i is 2*i+1 nums[2 * i] |= (x_i << 10); nums[2 * i + 1] |= (y_i << 10); } // 2. Decoding phase for (int i = 0; i < 2 * n; i++) { nums[i] = nums[i] >> 10; } return nums; }}Complexity
Time
O(n) - The encoding phase involves a loop that runs `n` times. The decoding phase involves a loop that runs `2n` times. Both loops perform constant time bitwise operations. The total time complexity is O(n) + O(2n), which simplifies to O(n).
Space
O(1) - The shuffle is performed in-place on the input array. No auxiliary data structures proportional to the input size are used.
Trade-offs
Pros
Extremely space-efficient, using O(1) extra space.
Maintains a linear time complexity.
Cons
The logic is significantly more complex and less intuitive than the extra array approach.
This solution is highly dependent on the constraints of the input values (i.e., they must be small enough to allow for encoding).
The code is less readable and harder to maintain.
Solutions
Solution
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 ; } }class Solution { public: vector < int > shuffle ( vector < int >& nums , int n ) { vector < int > ans ; for ( int i = 0 ; i < n ; ++ i ) { ans . push_back ( nums [ i ]); ans . push_back ( nums [ i + n ]); } return ans ; } };class Solution : def shuffle ( self , nums : List [ int ], n : int ) -> List [ int ]: ans = [] for i in range ( n ): ans . append ( nums [ i ]) ans . append ( nums [ i + n ]) return ansVideo 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.