384. Shuffle an Array
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 54.1%
Problem Breakdown
The problem asks us to implement a class that manages an array with three capabilities: initialization from input data, resetting back to the original state, and shuffling into a random configuration where every possible permutation has equal probability (uniform distribution).
Inputs: An integer list nums in the constructor.
Outputs: The constructor returns nothing (null). reset() returns the array as it was initialized. shuffle() returns a new shuffled version of the array.
Implicit Constraints & Edge Cases:
- Uniform Distribution: This is the most critical constraint. A naive shuffle (e.g., swapping with random index repeatedly) often results in biased permutations where some arrangements are more likely than others. We must ensure every permutation has probability .
- State Management: Since
reset()needs to return the original configuration, we cannot modify our internal storage permanently during a shuffle without keeping track of the initial state separately. - Constraints: Array length is small (up to 200), so or even slightly worse time complexity per call passes easily within limits ( calls). However, we aim for optimal efficiency.
- Data Types: Integers can be negative; Python handles this natively without overflow issues relevant to the algorithm logic (unlike fixed-size integer types in C++/Java which might require modulo arithmetic considerations if not careful with random generation ranges).
Intuition
A brute-force approach would be to generate all permutations and pick one randomly. This is impossible for even moderate . A naive alternative is iterating through the array, picking a random element from the remaining pool, and swapping it into place. However, if we simply swap nums[i] with a random index in [0, i-1], does that guarantee uniformity?
The key insight comes from Fisher-Yates Shuffle (also known as Knuth Shuffle). The logic is: iterate through the array positions and for each position , pick a random element from the remaining unshuffled portion of the array. By swapping nums[i] with a randomly chosen index where , we ensure that at step , any of the remaining elements has an equal chance to end up in position .
Why is this better?
- Time Complexity: It performs exactly one swap per element, resulting in time complexity. Generating all permutations would be factorial time.
- Space Complexity: We can perform the shuffle in-place (or on a copy) using only constant extra space for logic variables, though we need to store the original state separately to support
reset().
Approach
- Initialization (
__init__): Store a deep copy of the input array as an instance variable (e.g.,self.original). This preserves the initial configuration required byreset()without relying on external references that might be mutated or lost. - Reset Method: Simply return the stored original list reference. Since we never mutate this specific internal storage during shuffling, it remains valid for all calls to
shuffle(). - Shuffle Method: To avoid side effects where a previous shuffle corrupts our ability to reset (or if multiple independent shuffles are needed), create a new copy of the stored original array. Apply the Fisher-Yates algorithm on this temporary list:
- Iterate backwards from
n-1down to0. - For each index
i, generate a random integerjsuch that . - Swap elements at indices
iandj.
- Iterate backwards from
- Return: Return the shuffled list created in step 3.
Complexity Analysis
- Time Complexity:
- Constructor: to copy input.
- Reset: .
- Shuffle: because we iterate through the array once, performing constant work per element (random generation and swap).
- Overall for all calls within constraints remains efficient ( ops where K is call count).
- Space Complexity:
- to store the original configuration in memory (necessary for
reset). - auxiliary space beyond input/output storage during the shuffle logic itself. The returned array counts as output, not extra working memory.
- to store the original configuration in memory (necessary for
Solution
import random
class Solution:
def __init__(self, nums):
"""Initialize with a deep copy to preserve original state for reset."""
self.original = list(nums) # Store initial configuration
def reset(self):
"""Return the array in its original configuration."""
return self.original
def shuffle(self):
"""Perform Fisher-Yates shuffle on a fresh copy of the original data."""
arr = self.original[:] # Create working copy to avoid mutating stored state
n = len(arr)
for i in range(n - 1, 0, -1):
j = random.randint(0, i)
arr[i], arr[j] = arr[j], arr[i]
return arr
# Example usage logic (not part of class definition but helpful context if needed)
# solution = Solution([1,2,3])
# print(solution.shuffle()) # Returns shuffled list
# print(solution.reset()) # Returns [1, 2, 3]
Edge Cases Handled
- Single Element Array: The loop range
range(n - 1, 0, -1)handles correctly (loop does not execute), returning the single element as is. This satisfies uniform distribution for a set of size 1. - Negative Numbers / Large Values: Python integers handle arbitrary precision and negative values naturally; no overflow logic required beyond standard arithmetic operations used in swapping.
- Multiple Shuffles Without Reset: Since
shuffle()creates a new list from the stored original state (self.original), calling shuffle multiple times without resetting does not corrupt internal data or bias subsequent shuffles (each starts fresh based on the initial set). - Reset Consistency: By storing an immutable reference to the initial configuration in
__init__, every call toreset()returns a list that matches exactly what was passed during initialization, regardless of how many timesshufflehas been called.