Solving Popular Algorithms: Shuffle the Array

I feel like it’s been a while since I’ve actually sat down to solve an algorithm. I mean, it’s been over a week, which I guess is a long time on someone’s scale. Like a fly. A week is a very long time for a fly.

I don’t really know where I’m going with this, so instead let’s move on and get right into explaining the problem we are going to be solving today: Shuffle the Array.

Before we begin, I do want to quickly note that this problem is actually quite similar (though a lot easier…) to another very popular algorithm that you might have heard of called merge sort. So, if you are practicing for technical interviews and have yet to try merge sort, I’d definitely recommend warming up with this problem first!

Now, let’s get into solving.

A good boy doing a good shuffle

The Problem

For this problem, our function will take in two arguments. First, a number, n. And second, an array of numbers called nums that will contain 2n elements.

nums = [2,5,1,3,4,7], n = 3

The goal of our algorithm will be to take nums, split it in half and then, merge those two half together in an alternating pattern. To clarify, let’s look at our example above.

If we were to split that array in half, the first half would consist of the numbers 2, 5, and 1 while the second half would obviously be 3, 4, and 7. Then, we went to merge those halves, we would want to combine to make this array:

[2,3,5,4,1,7] 

As you can tell, we are alternating from which half a number is merged into our final array. Starting with the first half, we add 2. Then, from the second half, we add 3. Then back to the first with 5. And so on.

Now that we understand the goal of our problem, to return this merged array, let’s move onto solving it.

The solution: An overview

I’ve mentioned this before, but one of my best practices when it comes to solving algorithms, is, before I write any code, writing out how I intend to solve the problem in psuedocode. I find that this really helps me think through the steps of how to solve the problem and allows me get to solution not only easier, but generally a lot quicker as well.

So, for this problem, I realized my solution would basically have two steps. First, I would need to split our original array into two separate arrays each containing n elements. Second, I would need to merge those two arrays into one final array.

While this plan may seem simple, I’ve found that even having a super simple plan like this will really help me ultimately find the solution to any problem I’m working on.

The solution: Splitting Nums

Like I said above, my first step to solving this problem will be to split our original array, nums, into two separate arrays each containing n elements.

To accomplish this task, I create two separate for loops, each responsible for creating one array containing half the elements in nums.

For the first half of original nums, I created an empty array I called partOne. Then, starting at i = 0, since we want the first n elements in our array, and ending halfway through nums, we can push each element into partOne.

let partOne = []
for (let i = 0; i < nums.length/2; i++) {
   partOne.push(nums[i])
}

Our second for loop for the second half of our original array will work very similarly to the first for loop. The only difference will be where our loop starts and ends. Since we are now trying to get the second n elements in our array, we can start with j = n and loop simply until the end of our original nums array.

let partTwo = []
for (let j= n; j < nums.length; j++) {
   partTwo.push(nums[j])
}

Once we have both of those for loops written, we can move onto the second part of our solution: merging them back together.

The Solution: Merging

To merge our two new arrays, partOne and partTwo, we are going to rely on the JS method called shift. If you’re unfamiliar, shift removes elements from the start of an array and returns the element. Since, we are trying to merge elements together in an alternating pattern starting from the beginning of each array, shift will be incredibly useful.

Another helpful part of the shift method is that it is a destructive method meaning that it mutates the original array. In our case, this will again be very helpful as we can create a while loop that will run until both arrays contain zero elements and inside that loop we can use the shift method which will be removing elements from both arrays until our condition is met and the loop stops.

let finalArr = []
while (partOne.length > 0 && partTwo.length > 0) {
   finalArr.push(partOne.shift(), partTwo.shift()
}

The solution: Completed

Now that we understand how both parts of our solution work, here is our final code:

shuffle = (nums, n) => {
   let partOne = []
   for (let i = 0; i < nums.length/2; i++) {
      partOne.push(nums[i])
   }
   let partTwo = []
   for (let j= n; j < nums.length; j++) {
      partTwo.push(nums[j])
   }
   let finalArr = []
   while (partOne.length > 0 && partTwo.length > 0) {
      finalArr.push(partOne.shift(), partTwo.shift()
   }
   return finalArr
}

Like I said at the start of this post, this problem is great practice for other harder problems like merge sort, so I’d definitely recommend giving it a try on your own!

Like always, good luck and happy coding!

Happy dancing for two reasons: 1) I solved this problem and 2) I won another game in my fantasy league!