Shuffle an Array — Fisher-Yates O(n) Uniform Shuffle [Google Easy]

Problem Statement#

LeetCode 384 — Shuffle an Array

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

• Solution(int[] nums) — initializes the object with the original array nums
• int[] reset() — resets the array to its original configuration and returns it
• int[] shuffle() — returns a random shuffling of the array

Example:

Input:
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
 
Output:
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Constraints:

• 1 <= nums.length <= 50
• -10^6 <= nums[i] <= 10^6
• All elements of nums are unique
• At most 10^4 calls will be made to reset and shuffle

Why This Problem Matters#

At first glance this feels trivial — just pick random indices and swap, right? But this problem is a classic Google and FAANG interview staple because it exposes a subtle trap: nearly every intuitive approach is statistically biased. Getting it wrong in an interview won't just cost you the problem — it signals that you don't think carefully about correctness guarantees.

The reason this problem matters beyond LeetCode:

1. Real-world consequence. Every card game, A/B test assignment, playlist shuffle, and randomized algorithm depends on uniform shuffling. A biased shuffle in a poker application gives some hands an unfair edge. A biased shuffle in an A/B test invalidates the experiment.

2. Probability intuition under pressure. Interviewers use this problem to probe whether you understand why a solution is correct — not just whether it passes test cases. They will ask follow-ups like "prove it's uniform" or "what's wrong with using sort with a random comparator?"

3. In-place algorithm design. The optimal solution uses O(1) extra space while still being correct. Many candidates default to O(n) approaches that allocate a new array each time.

4. Class design. Unlike most LeetCode problems, this one tests your ability to design a stateful class with multiple methods — a pattern common in real system design interviews.

Understanding Fisher-Yates deeply — including why naive alternatives fail — is the difference between a "hire" and a "no hire" signal on this problem.

The Fisher-Yates Algorithm Explained#

Why Naive Random Is Biased#

The most intuitive approach a candidate reaches for is something like this:

# WARNING: This is BIASED — do not use in production or interviews
def naive_shuffle(nums):
    n = len(nums)
    for i in range(n):
        j = random.randint(0, n - 1)  # BUG: range spans the ENTIRE array
        nums[i], nums[j] = nums[j], nums[i]
    return nums

This looks correct. It isn't. Here's why.

For an array of length n, there are exactly n! possible permutations. A correct shuffle must give each permutation probability 1 / n!.

The naive approach above makes n independent random choices, each from n possibilities, producing n^n total equally-likely execution paths. For n = 3, that is 3^3 = 27 paths for 3! = 6 permutations. Since 27 is not divisible by 6, it is mathematically impossible to distribute 27 paths evenly across 6 permutations. Some permutations will always appear more often than others, no matter what.

Enumerating all 27 paths for [1, 2, 3]:

• The identity permutation [1, 2, 3] appears 4 times — probability 4/27 ≈ 14.8%
• Three other permutations each appear 5 times — probability 5/27 ≈ 18.5%
• The remaining two permutations appear fewer times

The bias is real and measurable. In small arrays it is a subtle skew; at scale it becomes a serious statistical defect.

Another famously broken approach: using array.sort(key=lambda x: random.random()). The problem here is that the random keys are generated once, but comparison-based sorting makes multiple comparisons per element. The order in which comparisons happen interacts with the random keys in ways that break uniformity. This was infamously the bug in an old Microsoft browser ballot shuffling algorithm.

How Fisher-Yates Achieves Perfect Uniformity#

The Fisher-Yates algorithm (also called the Knuth shuffle) fixes the bias with one key insight:

At step i, pick a random element from the UNSHUFFLED portion only — indices 0 through i inclusive — and lock it into position i.

The modern (Knuth) version, iterating from the end:

for i from n-1 downto 1:
    j = random integer in [0, i]   (inclusive on both ends)
    swap nums[i] and nums[j]

Why is this uniform? Consider placing element into the last position first:

• Each of the n elements has probability 1/n of being chosen for position n-1.
• After that choice, each of the remaining n-1 elements has probability 1/(n-1) of being chosen for position n-2.
• Continuing: 1/n * 1/(n-1) * 1/(n-2) * ... * 1/1 = 1/n!

Every permutation has exactly probability 1/n!. The algorithm makes exactly n-1 swaps and n-1 random number calls — no more, no less.

The two versions of Fisher-Yates are equivalent:

Both are correct. The Knuth version is more common in interviews. The critical invariant either way: you never pick from the already-shuffled region.

Visual Dry Run#

Let's trace through nums = [1, 2, 3, 4] step by step using the Knuth version (right to left).

Initial state:

Index:  0   1   2   3
Value: [1,  2,  3,  4]
                    ^
                 i = 3 (current position)

Step 1: i = 3

• Pick random j in [0, 3]. Say j = 1.
• Swap nums[3] and nums[1].

Before: [1,  2,  3,  4]
                    ^i  ^was j=1
After:  [1,  4,  3,  2]
                    ^-- 2 is now locked in place

Unshuffled region: indices 0..2. Shuffled region: index 3.

Step 2: i = 2

• Pick random j in [0, 2]. Say j = 0.
• Swap nums[2] and nums[0].

Before: [1,  4,  3,  2]
                ^i
After:  [3,  4,  1,  2]
                ^-- 1 is now locked in place

Unshuffled region: indices 0..1. Shuffled region: indices 2..3.

Step 3: i = 1

• Pick random j in [0, 1]. Say j = 1.
• Swap nums[1] with itself (no change — this is allowed and necessary for uniformity).

Before: [3,  4,  1,  2]
            ^i
After:  [3,  4,  1,  2]
            ^-- 4 is now locked in place

Unshuffled region: index 0 only. Shuffled region: indices 1..3.

Final result: [3, 4, 1, 2]

The element at index 0 stays wherever it ended up — no step needed since there is only one choice remaining. This is why the loop runs from n-1 down to 1 (not 0).

Key observation: At every step, the random index j is strictly bounded to the unshuffled region. The already-locked elements are never touched again. This is what guarantees uniformity.

Common Mistakes#

Mistake 1: Wrong random range (off-by-one)#

# WRONG — j should go up to i (inclusive), not i-1
j = random.randint(0, i - 1)

This prevents any element from staying in its original position during that step, which breaks uniformity. The element at index i can never be "chosen" for position i, so permutations where an element stays put are underrepresented.

Mistake 2: Picking from the entire array (naive shuffle)#

# WRONG — j should be bounded by i, not n-1
j = random.randint(0, len(nums) - 1)

This is the biased naive shuffle discussed above. It runs n^n execution paths for n! permutations, which cannot be distributed evenly when n > 2.

Mistake 3: Mutating the original array in reset()#

# WRONG — this shares a reference, not a copy
self.original = nums

If self.nums and self.original point to the same list object, shuffling self.nums will also corrupt self.original. Always store a deep copy at construction time using nums[:] (Python) or the spread operator [...nums] (JavaScript).

Mistake 4: Using sort with a random comparator#

# WRONG — biased, and also violates sort contract (non-transitivity)
nums.sort(key=lambda x: random.random())

Beyond the bias problem, comparison-based sorting assumes transitivity: if a > b and b > c, then a > c. When comparisons are random, this property is violated, which causes undefined behavior in many sort implementations and can even cause infinite loops.

Mistake 5: Stopping the loop at i = 0 when iterating left-to-right (off by one direction)#

When iterating left to right, the loop should go from i = 0 to i = n - 2 (not n - 1). When you reach the last element there is only one choice — it stays — so including it adds no randomness but also doesn't break correctness. However, calling the random number generator unnecessarily is wasteful.

Solutions#

Python#

import random
 
class Solution:
 
    def __init__(self, nums: list[int]):
        # Store the original array as an immutable reference point.
        # We use a slice copy (nums[:]) so self.original is independent
        # of whatever list the caller passes in later.
        self.original = nums[:]
 
        # self.nums is the working copy we will shuffle in place.
        self.nums = nums[:]
 
    def reset(self) -> list[int]:
        # Restore the working copy from the original snapshot.
        # We copy again so future shuffles don't corrupt self.original.
        self.nums = self.original[:]
        return self.nums
 
    def shuffle(self) -> list[int]:
        n = len(self.nums)
 
        # Fisher-Yates (Knuth) shuffle — iterate from the last index down to 1.
        for i in range(n - 1, 0, -1):
            # Pick a random index j from the UNSHUFFLED region [0, i] inclusive.
            # Using i + 1 as the upper bound because randint is inclusive on both ends
            # but random.randrange(0, i+1) is more idiomatic in some contexts.
            j = random.randint(0, i)
 
            # Swap element at position i with element at position j.
            # After this swap, position i is "locked" and never touched again.
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
 
        return self.nums

Why range(n - 1, 0, -1)? The loop stops at i = 1 because when only one element remains (index 0), there is exactly one choice — it stays in place. Including i = 0 would call random.randint(0, 0) which always returns 0, adding no randomness.

JavaScript#

class Solution {
    /**
     * @param {number[]} nums
     */
    constructor(nums) {
        // Store an independent copy of the original array.
        // Spread operator [...nums] creates a shallow copy — sufficient here
        // because all elements are primitives (integers).
        this.original = [...nums];
 
        // Working copy that we will shuffle in place.
        this.nums = [...nums];
    }
 
    /**
     * Resets the array to its original configuration and returns it.
     * @return {number[]}
     */
    reset() {
        // Restore from the original snapshot by making a fresh copy.
        this.nums = [...this.original];
        return this.nums;
    }
 
    /**
     * Returns a random shuffling of the array.
     * @return {number[]}
     */
    shuffle() {
        const n = this.nums.length;
 
        // Fisher-Yates (Knuth) shuffle — walk from the last index down to 1.
        for (let i = n - 1; i > 0; i--) {
            // Pick a uniformly random index j in [0, i] inclusive.
            // Math.random() returns [0, 1), so Math.floor(Math.random() * (i + 1))
            // produces integers in {0, 1, ..., i} with equal probability.
            const j = Math.floor(Math.random() * (i + 1));
 
            // Swap nums[i] and nums[j] using destructuring assignment.
            // After this, index i is locked into its final shuffled position.
            [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
        }
 
        return this.nums;
    }
}

JavaScript note: Unlike Python's random.randint(0, i) which is inclusive on both ends, JavaScript's Math.random() returns a float in [0, 1). Multiplying by (i + 1) and flooring gives an integer in [0, i] with uniform probability — do not use Math.round() here, as that would give the endpoints (0 and i) half the probability of interior values.

Complexity Analysis#

Space discussion: The O(n) space is unavoidable — we must store the original array to support reset(). The shuffle itself uses only O(1) extra space beyond the stored arrays. Some candidates mistakenly allocate a new array inside shuffle() each call; this is O(n) extra per call and unnecessary.

Can we do better than O(n) per shuffle? No. Any correct uniform shuffle must "touch" every element at least once (otherwise some elements have zero probability of moving), which implies a lower bound of O(n).

Follow-up Questions#

These are real questions FAANG interviewers ask after the initial solution:

1. "Prove that your shuffle is uniform."

For any specific target permutation P, trace through the algorithm: the probability that element P[n-1] was chosen for position n-1 is 1/n. Given that, the probability P[n-2] was chosen for position n-2 is 1/(n-1). Multiplying: 1/n * 1/(n-1) * ... * 1/1 = 1/n!. Since every permutation has the same probability 1/n!, the shuffle is uniform.

2. "What if random.randint itself is biased? How would you test your shuffle?"

Run the shuffle a large number of times (say, 1,000,000) on a small array (say, [1, 2, 3]), count the frequency of each of the 6 permutations, and perform a chi-squared goodness-of-fit test. Each permutation should appear roughly 1/6 of the time; the chi-squared statistic tells you whether deviations are within expected random variation.

3. "What if the array is too large to fit in memory?"

Use a sparse Fisher-Yates variant: maintain a hash map that records swaps. Only entries that differ from their original index need to be stored. This allows lazy shuffling of huge virtual arrays where you only materialize elements as needed.

4. "How would you generate a random sample of k elements from the array without replacement?"

Run Fisher-Yates for only the first k steps (from index n-1 down to n-k). The last k positions contain a uniform random sample of size k. This is Knuth's "Algorithm S" and runs in O(k) time — you don't need to shuffle the full array.

5. "What's wrong with array.sort(() => Math.random() - 0.5) in JavaScript?"

Two problems: (a) it produces a biased shuffle because sort makes O(n log n) comparisons and the random outcomes of those comparisons interact in non-uniform ways; (b) it violates the transitivity contract of a comparator, which can cause V8's sort implementation to behave unpredictably (including generating non-random orderings on certain inputs).

6. "Can you make reset() O(1)?"

No, not while also keeping shuffle() correct. If reset() is O(1), it means we didn't copy the array — but then shuffle() would corrupt whatever we returned from reset(). The O(n) copy in reset() is necessary for correctness.

This Pattern Solves#

Fisher-Yates and the "pick from remaining" insight appear in many related problems:

• Random pick with weights (LC 528): Fisher-Yates intuition extended to non-uniform probabilities using prefix sums and binary search.
• Linked list random node (LC 382): Reservoir sampling — a streaming generalization of Fisher-Yates where you maintain a uniform random sample as you stream through unknown-length input.
• Random pick index (LC 398): Reservoir sampling again, but for repeated elements.
• Generate random permutation: Direct application — Fisher-Yates is the standard answer.
• Online algorithm / streaming shuffle: Reservoir sampling is the generalization when n is not known in advance.
• Randomized QuickSort / QuickSelect: Random pivot selection uses the same "pick uniformly from remaining" principle.

The core insight — shrink the candidate pool after each pick — appears everywhere you need to generate fair random selections without replacement.

Key Takeaways#

• LeetCode 384 — Shuffle an Array is a Medium design problem asked at Google and Amazon; Fisher-Yates is the only correct O(n) uniform shuffle.
• Fisher-Yates: at each step i, pick a random index j from [i, n-1] and swap — this creates exactly n! execution paths, one per permutation.
• The naive approach (pick from [0, n-1] each time) generates n^n paths, which doesn't divide evenly into n! for n > 2 — mathematically biased.
• Time O(n) for shuffle and reset; space O(n) to store the original array for reset.
• Always store a copy of the original array in the constructor so reset() can return to it without re-sorting.
• The random(i, n-1) range is crucial: picking from the entire array on each step introduces the bias interviewers are testing for.
• Fisher-Yates is used in production for every shuffle — interview candidates who know this show both CS fundamentals and practical engineering awareness.

3. The random range must be [0, i] inclusive — using [0, i-1] is an off-by-one that re-introduces bias.

These three points alone demonstrate the depth of understanding interviewers are looking for.