LeetCode 1470. Shuffle the Array

September 11, 2020

We have to touch each element at least once to do this zip-shuffle thing, so our best possible runtime is $O(n)$ .

We can do this in $O(n)$ with:

Two pointers, one to the start of the array and one to the half way point ( $y_1$ ).
Iterate over both pointers together, adding alternating elements to our output list.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.shuffle([2,5,1,3,4,7], 3), [2,3,5,4,1,7])
        self.assertEqual(self.s.shuffle([1,2,3,4,4,3,2,1], 4), [1,4,2,3,3,2,4,1])
        self.assertEqual(self.s.shuffle([1,1,2,2], 2), [1,2,1,2])

    def test_empty(self):
        self.assertEqual(self.s.shuffle([], 0), [])

class Solution:

    def shuffle(self, nums: List[int], n: int) -> List[int]:
        out = []
        for i in range(n):
            out.append(nums[i])
            out.append(nums[i+n])
        return out

if __name__ == "__main__":
    unittest.main()