Domain 2MediumCORE

Shuffle an Array

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).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

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:

  1. 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 1/n!1/n!.
  2. 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.
  3. Constraints: Array length is small (up to 200), so O(N)O(N) or even slightly worse time complexity per call passes easily within limits (5×1045 \times 10^4 calls). However, we aim for optimal efficiency.
  4. 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 N!N! permutations and pick one randomly. This is impossible for even moderate NN. 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 ii, pick a random element from the remaining unshuffled portion of the array. By swapping nums[i] with a randomly chosen index jj where 0≤j≤i0 \le j \le i, we ensure that at step ii, any of the remaining elements has an equal chance to end up in position ii.

Why is this better?

  1. Time Complexity: It performs exactly one swap per element, resulting in O(N)O(N) time complexity. Generating all permutations would be factorial time.
  2. 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

  1. Initialization (__init__): Store a deep copy of the input array as an instance variable (e.g., self.original). This preserves the initial configuration required by reset() without relying on external references that might be mutated or lost.
  2. 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().
  3. 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-1 down to 0.
    • For each index i, generate a random integer j such that 0≤j≤i0 \le j \le i.
    • Swap elements at indices i and j.
  4. Return: Return the shuffled list created in step 3.

Complexity Analysis

  • Time Complexity:
    • Constructor: O(N)O(N) to copy input.
    • Reset: O(1)O(1).
    • Shuffle: O(N)O(N) because we iterate through the array once, performing constant work per element (random generation and swap).
    • Overall for all calls within constraints remains efficient (5×1045 \times 10^4 ops ≈O(K⋅N)\approx O(K \cdot N) where K is call count).
  • Space Complexity:
    • O(N)O(N) to store the original configuration in memory (necessary for reset).
    • O(1)O(1) auxiliary space beyond input/output storage during the shuffle logic itself. The returned array counts as output, not extra working memory.

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 N=1N=1 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 to reset() returns a list that matches exactly what was passed during initialization, regardless of how many times shuffle has been called.