The problem Shuffle the Array Leetcode Solution provides us with an array of length 2n. Here 2n refers that the array length is even. We are then told to shuffle the array. Here shuffling does not mean that we need to randomly shuffle the array but a specific way is shown. If the given array can be represented as [x1, x2, …, y1, y2, …] then the shuffling is represented as [x1, y1, x2, y2, …]. So the problem is pretty straight forward and does not expect us to solve anything. We are simply required to find some way to swap the elements to get the required sequence. There is also one constraint over the input, the input elements are less than 10^3. But before diving deep into the solution, let us take a loop at a few examples.
nums = [2,5,1,3,4,7], n = 3
[2,3,5,4,1,7]
Explanation: We easily verify that the output satisfies the required criteria as imposed in the problem. If we assign naming such as x1, x2, until y3 to the elements of the array. We can see that the elements are now arranged in the [x1, y1, x2, y2, x3, y3] fashion.
Table of Contents
Approach for Shuffle the Array Leetcode Solution
The problem Shuffle the Array Leetcode Solution asks to shuffle the array in a specific manner. The shuffling fashion asks us to place the last half elements of the array between the elements of the first half. More formally, an array [x1, x2, x3, …, y1, y2, y3, …] is to be shuffled as [x1, y1, x2, y2, x3, y3, …xn, yn]. So one can easily solve the problem with the help of additional space. Because then we can simply create a new array of the same length as that of the original one. And push the elements from the first half then the second half. This way we end up with the required array.
To solve the problem without any additional space that is in O(1) space. We need to take help from binary manipulation. This may seem like a trick because these algorithms are not seen very often. Thus these problems fall under the category of ad-hoc. The first step to solve the problem is to somehow combine the elements from the first and second half into the second half. But what does this COMBINE means? We first shift the elements from the second half to the left (left binary shift) by 10 bits. Then either we add the elements of the first half or we take OR of the elements of the second half with the elements of the first half. so now the elements are combined.
Now simply traverse over the original array. We start a for loop that increments 2 steps in each iteration. In each step we pick an element from the second half and replace the elements at these places with the xi, yi. We can get the xi, yi by first taking AND of the elements in the second half with 2^10-1 to get the first element. As for the second element, we right shift each element by 10 bits.
Code for Shuffle the Array Leetcode Solution
C++ code
#include <bits/stdc++.h>
using namespace std;
vector<int> shuffle(vector<int>& nums, int n) {
for(int i=n;i<2*n;i++){
nums[i] = nums[i]<<10;
nums[i] |= nums[i-n];
}
int z = n;
for(int i=0;i<2*n;i+=2){
nums[i] = nums[z] & 1023;
nums[i+1] = nums[z++] >> 10;
}
return nums;
}
int main() {
vector<int> input = {2,5,1,3,4,7};
int n = 3;
vector<int> output = shuffle(input, n);
for(auto x: output)
cout<<x<<" ";
}2 3 5 4 1 7
Java code
import java.util.*;
import java.io.*;
class Main {
private static int[] shuffle(int[] nums, int n) {
for(int i=n;i<2*n;i++){
nums[i] = nums[i]<<10;
nums[i] |= nums[i-n];
}
int z = n;
for(int i=0;i<2*n;i+=2){
nums[i] = nums[z] & 1023;
nums[i+1] = nums[z++] >> 10;
}
return nums;
}
public static void main(String[] args) {
int[] input = {2,5,1,3,4,7};
int n = 3;
int[] output = shuffle(input, n);
for(int i=0;i<2*n;i++)
System.out.print(output[i]+" ");
}
}
2 3 5 4 1 7
Complexity Analysis
Time Complexity
O(N), since we traverse each element of the array. Even though we are provided with 2n elements, the time complexity still remains to be O(N).
Space Complexity
O(1), the algorithm is an in-place algorithm. Thus the space complexity is also constant.