Problem statement

https://leetcode.com/problems/shuffle-an-array/

Solution

In this problem we need to shuffle given array and there are different ways to do it. The most optimal algorithm is called Fisher-Yates Algorithm, where we swap original array elements. The idea is to do several steps:

  1. Take i = 0 and then generate random index from [0, n-1] and swap these two elements.
  2. Take i = 1 and then generate random index from [1, n-1] and swap these two elements. …

Actually this code is for Fisher-Yates with indexes from lowest to highest, classical one is in opposite direction, but this one a bit easirer to code. It is not obvious why this algorithm will generate all shuffles with the same probability, but it can be solved by induction, see wikipedia for more details.

Complexity

Time complexity is O(n) both for reset and shuffle. Space complexity is O(n).

Code

class Solution:
    def __init__(self, nums):
        self.nums = nums[:]
        self.copy = nums[:]

    def reset(self):
        self.nums = self.copy[:]
        return self.nums
        
    def shuffle(self):
        n = len(self.nums)
        for i in range(n):
            j = randint(i, n - 1)
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums