Shuffle the Array (Javascript)

#javascript #algorithms

Algorithms are something I struggle with. A few of the interviews or screening processes for companies I've done recently have involved algorithms. Being eliminated before even getting to speak to someone is very discouraging. In response, I'm being intentional about solving algorithms recently. This time I'll be tackling this Leetcode 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].

My job is to shuffle the elements of the array together like a deck of cards. This problem is simple with Javascripts .push() method.

var shuffle = function(nums, n) {
    let arr = [];
    for ( let i=0; i<n; i++ ) {
        arr.push(nums[i], nums[i+n])
    };
    return arr;
};

Declare an empty array arr which will be my return value.
Begin a for loop that will run until the index is greater than n.
In each iteration:
1. push() the current index nums[i] and nums[i + n] into the return array arr.

After iterating n times return our new array.

The difficulty was increased when I approached it without push(). I was having trouble keeping track of the indexes I need access to, so I wrote it out on a whiteboard. After writing it out I was able to find the pattern. Stepping through every iteration really cleared up what counters I needed.

I ended up with four variables i, y, x, b. i pointed to the first index for the return array of my code block. y pointed to the second index for the return array. These two variables were incremented by 2 each iteration. x pointed to the first index for the input array. b pointed to the second index for the input array. These two variables were incremented by 1 each iteration. To catch the pattern I really needed to be thorough. After that I was quickly able to deduce what I needed to do. This was my final solution:

var shuffle = function(nums, n) {
    const arr = [];
    let i = 0
    for ( let x=0; x < n; x++) {
        arr[i] = nums[x];
        arr[i+1] = nums[x+n];
        i+=2;
    };
    return arr;
};

Declare an empty array arr which will be my return value.
Declare a counter i outside of the loop that I'll increment differently.
Begin a for loop that will run until the index x is greater than n.
In each iteration:
1. Set arr[i] to nums[x]
2. Set arr[i+1] to nums[x+n]
3. Increment i by 2
4. Check if x < n
Return the array.

Top comments (3)

pentacular • Aug 27 '20

When I see this kind of problem, my first thought is to see if it can be decomposed into a couple of simpler problems.

Here I think we can turn it into 'partition' and 'zip', and I think this is the insight that I'd be looking for if I were asking this as an interview question.

const partition = (array) => [array.slice(0, array.length / 2), array.slice(array.length / 2)];

const zip = (a, b) => {
  const zipped = [];
  const limit = Math.max(a.length, b.length);
  for (let nth = 0; nth < limit; nth++) {
    if (a[nth] !== undefined) {
      zipped.push(a[nth]);
    }
    if (b[nth] !== undefined) {
      zipped.push(b[nth]);
    }
  }
  return zipped;
}

const shuffle = (array) => zip(...partition(array));

I'd then have a conversation about efficiency, and might come up with a composed version closer to what you've shown above, if the interviewer were interested in following that path.

Anyhow, just thought I'd offer another perspective -- good luck. :)