Initially, it may seem that this question is trivial. If we have an array in the format [x1, x2, … xN, y1, y2, … yN] and we’re trying to do some swaps to make the array [x1, y1, x2, y2, …]. You could simply declare a new array and put the x’s and y’s in the right slots in the new array. It’s O(n) time with O(n) auxiliary space.

      func shuffle(nums []int, n int) []int {
         shuffled := make([]int, 2*n)
         for i, j := 1, 0; i<len(nums); i, k, l = i+2, j+1 {
             shuffled[i-1] = nums[j]
             shuffled[i] = nums[j+n]
         }
         return shuffled
      }
    

The question that now comes to mind is how can we do this in-place without auxiliary O(n) space? Conceptually, it seems pretty easy. Surely, we can find a way to just swap the numbers into the right place and then put them back? But, truth be told, I really struggled with how to do that.

I found an good example written in Ruby but was initially stumped by the explaination. So, I decided to investigate further.

Let’s first think about the array. The primary hint is the problem specifies that all the numbers are all greater than zero. Therefore, we could negate a number to show it’s in the correct place. Furthermore, we don’t care about the first and last elements because they’re already in the last place. So, we can devise an algorithm where “slots” are successively used for storing the swapped numbers until the slot is taken up by the correct number. Then we move to the next slot. This algorithm is O(n) time because each move we are always putting a number into the correct place. It’s O(1) auxiliary space because we do not need an additional array.

      func getDesiredIndex(j, n int) int {
          if j < n {
              return j*2
          }
          return (j-n)*2+1
      }
      
      func slotAvailable(nums []int, i int) bool {
          return nums[i] >= 0
      }
      
      func shuffle(nums []int, n int) []int {
         for i := 1; i < len(nums)-1; i++ {
            j := i
            for slotAvailable(nums, i) {
               j = getDesiredIndex(j, n)
               nums[i], nums[j] = nums[j], -nums[i]
            }
         }
         for i := 1; i < len(nums)-1; i++ {
             nums[i] = -nums[i]
         }
      }
    

So, for the above example, if we have [2,5,1,3,4,7] then we will use first index 1 as our first slot. We will swap x2 i.e. the 5 to its desired index which is 2. Then our array will look like [2, 1, -5, 3, 4, 7]. We’re still using index 1 as our slot, but our desired index is now 4. We swap again and our array looks like [2, 4, -5, 3, -1, 7]. So, we’re now into the y’s section of the array so our desired index is 3. We swap again and our array is [2, 3, -5, -4, -1, 7]. Next, our desired index is 1. So, swapping, our array is [2, -3, -5, -4, -1, 7]. Thus, swapping is complete. We negate the negative values and our final array is [2, 3, 5, 4, 1, 7]. Didn’t we only use index 1 as our slot? That’s true for the example I gave, but for larger arrays this is not the case.