Problem Description

This problem asks you to implement a class that can shuffle an integer array randomly while maintaining the ability to reset it to its original state.

You need to create a Solution class with three methods:

1. Constructor __init__(nums): Takes an integer array nums as input and initializes the object with this array.

2. reset() method: Returns the array back to its original configuration (the state it was in when first passed to the constructor).

3. shuffle() method: Returns a randomly shuffled version of the array. The key requirement is that all possible permutations of the array must have an equal probability of occurring.

The implementation uses the Fisher-Yates shuffle algorithm (also known as Knuth shuffle):

• In the __init__ method, both the working array (self.nums) and a copy of the original array (self.original) are stored
• The reset() method creates a fresh copy of the original array and returns it
• The shuffle() method iterates through each position i in the array, randomly selects an index j from the range [i, n) where n is the array length, and swaps the elements at positions i and j

This algorithm ensures that each of the n! possible permutations has an equal probability of 1/n! of being generated, satisfying the "equally likely" requirement. The time complexity for shuffling is O(n) and space complexity is O(n) for storing the original array.

Intuition

The core challenge is generating a truly random shuffle where each possible arrangement has equal probability. Think about how you'd shuffle a deck of cards by hand - you'd pick cards randomly and rearrange them.

The naive approach might be to randomly pick two positions and swap them, repeating this many times. However, this doesn't guarantee uniform distribution of all permutations.

The key insight comes from building the shuffled array position by position. For each position i, we need to decide which element should go there. To ensure fairness, we should give every remaining element (from position i to the end) an equal chance of being selected.

This leads us to the Fisher-Yates algorithm logic:

• At position 0, any of the n elements could be first, so we pick from [0, n-1]
• At position 1, we pick from the remaining unplaced elements [1, n-1]
• At position i, we pick from [i, n-1]

By swapping the randomly chosen element with position i, we're essentially "placing" that element in its final shuffled position and then moving on to the next position.

The mathematical proof: For an array of length n, there are n! possible permutations. At each step i, we have (n-i) choices. So the total number of different outcomes is n × (n-1) × (n-2) × ... × 1 = n!, and since each choice is made uniformly at random, each permutation has probability 1/n!.

For the reset functionality, we simply need to maintain a copy of the original array. When reset is called, we restore from this preserved copy, allowing us to shuffle multiple times from the same starting point.

Solution Approach

The implementation consists of three main components:

1. Initialization (__init__ method):

def __init__(self, nums: List[int]):
    self.nums = nums
    self.original = nums.copy()

• Store the input array in self.nums for manipulation
• Create a deep copy of the original array in self.original to preserve the initial state
• Using .copy() is crucial here - without it, both variables would reference the same list, and modifications to one would affect the other

2. Reset functionality (reset method):

def reset(self) -> List[int]:
    self.nums = self.original.copy()
    return self.nums

• Create a fresh copy of the original array and assign it to self.nums
• Return the reset array
• Again, .copy() is essential to avoid modifying the preserved original

3. Shuffle implementation (shuffle method):

def shuffle(self) -> List[int]:
    for i in range(len(self.nums)):
        j = random.randrange(i, len(self.nums))
        self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
    return self.nums

• Iterate through each position i from 0 to n-1
• For each position i, randomly select an index j from the range [i, len(self.nums))
  • random.randrange(i, len(self.nums)) returns a random integer in [i, n-1]
• Swap elements at positions i and j using Python's tuple unpacking syntax
• After the loop completes, return the shuffled array

Time and Space Complexity:

• __init__: O(n) time and O(n) space for copying the array
• reset(): O(n) time for copying, O(1) additional space
• shuffle(): O(n) time for the single pass through the array, O(1) additional space
• Overall space: O(n) for storing the original array copy

The algorithm guarantees uniform randomness because at each step i, every element from position i onward has an equal probability 1/(n-i) of being placed at position i.

Example Walkthrough

Let's walk through the solution with a small array [1, 2, 3] to understand how the Fisher-Yates shuffle works:

Initial Setup:

solution = Solution([1, 2, 3])
# self.nums = [1, 2, 3]
# self.original = [1, 2, 3] (a separate copy)

First Shuffle Call: Let's trace through one possible execution of shuffle():

# Initial: nums = [1, 2, 3]

# Iteration i=0:
# - Pick random j from range [0, 3): suppose j=2
# - Swap nums[0] with nums[2]
# - Result: nums = [3, 2, 1]

# Iteration i=1:
# - Pick random j from range [1, 3): suppose j=1
# - Swap nums[1] with nums[1] (no change)
# - Result: nums = [3, 2, 1]

# Iteration i=2:
# - Pick random j from range [2, 3): only option is j=2
# - Swap nums[2] with nums[2] (no change)
# - Result: nums = [3, 2, 1]

# Return: [3, 2, 1]

Reset Call:

solution.reset()
# Creates new copy from self.original
# self.nums = [1, 2, 3]
# Returns: [1, 2, 3]

Second Shuffle Call: Another possible execution starting fresh from [1, 2, 3]:

# Initial: nums = [1, 2, 3]

# Iteration i=0:
# - Pick random j from range [0, 3): suppose j=0
# - Swap nums[0] with nums[0] (no change)
# - Result: nums = [1, 2, 3]

# Iteration i=1:
# - Pick random j from range [1, 3): suppose j=2
# - Swap nums[1] with nums[2]
# - Result: nums = [1, 3, 2]

# Iteration i=2:
# - Pick random j from range [2, 3): only option is j=2
# - Swap nums[2] with nums[2] (no change)
# - Result: nums = [1, 3, 2]

# Return: [1, 3, 2]

Why This Works: For an array of length 3, there are 3! = 6 possible permutations:

• [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

The algorithm makes:

• 3 choices for position 0 (any of the 3 elements)
• 2 choices for position 1 (from the remaining 2 elements)
• 1 choice for position 2 (the last element)

Total outcomes: 3 × 2 × 1 = 6, matching the number of permutations. Since each choice is random and independent, each permutation has probability 1/6.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(n) where n is the length of the input array, due to copying the array with nums.copy()
• reset(): O(n) because it creates a copy of the original array using self.original.copy()
• shuffle(): O(n) for the Fisher-Yates shuffle algorithm, which iterates through the array once and performs constant-time swaps

Space Complexity:

• Overall space: O(n) for storing two copies of the array (self.nums and self.original)
• __init__: O(n) additional space for storing the copy of the original array
• reset(): O(1) additional space (not counting the space already used by the object)
• shuffle(): O(1) additional space as it shuffles in-place using only a constant amount of extra variables

The shuffle algorithm implements the Fisher-Yates shuffle (also known as Knuth shuffle), which generates each permutation with equal probability 1/n! where n is the array length.

Common Pitfalls

1. Not Creating Proper Copies of the Array

The Pitfall: A very common mistake is storing references instead of copies:

def __init__(self, nums: List[int]):
    self.nums = nums
    self.original = nums  # WRONG! Both variables point to the same list

When you assign self.original = nums without .copy(), both variables reference the same list object in memory. Any modifications to self.nums during shuffling will also modify self.original, making it impossible to reset to the true original state.

The Solution: Always use .copy() to create independent copies:

def __init__(self, nums: List[int]):
    self.nums = nums
    self.original = nums.copy()  # Creates a separate copy

2. Incorrect Random Range in Shuffle

The Pitfall: Using the wrong range for random selection can create biased shuffles:

def shuffle(self) -> List[int]:
    for i in range(len(self.nums)):
        j = random.randrange(0, len(self.nums))  # WRONG! Creates bias
        self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
    return self.nums

Selecting from the entire array [0, n) instead of [i, n) doesn't guarantee uniform distribution of permutations.

The Solution: Always select from the remaining unshuffled portion:

j = random.randrange(i, len(self.nums))  # Correct: select from [i, n)

3. Forgetting to Copy in Reset Method

The Pitfall: Returning or assigning the original array directly without copying:

def reset(self) -> List[int]:
    self.nums = self.original  # WRONG! Now both reference the same list
    return self.nums

This creates the same reference problem - future shuffles would modify the "original" array.

The Solution: Create a fresh copy when resetting:

def reset(self) -> List[int]:
    self.nums = self.original.copy()
    return self.nums

4. Using random.choice() or random.sample() Incorrectly

The Pitfall: Trying to use high-level random functions without proper implementation:

def shuffle(self) -> List[int]:
    self.nums = random.sample(self.nums, len(self.nums))  # Works but less educational
    return self.nums

While random.sample() works, it doesn't demonstrate understanding of the Fisher-Yates algorithm, which is often the learning objective.

The Solution: Implement the Fisher-Yates algorithm manually to show algorithmic understanding and have full control over the shuffling process.