Shuffle an Array: The Fisher-Yates Algorithm

LeetCode Shuffle an Array (problem 384) asks you to design a class that can randomly shuffle an integer array so that every permutation is equally likely. You also need a reset() method that returns the array to its original configuration.

The trap here is not writing a shuffle. It is writing a correct one. Most naive approaches produce biased results where some permutations appear more often than others. The Fisher-Yates algorithm is the standard way to avoid that bias.

The key insight

If you iterate from the end of the array to the beginning and swap each element with a randomly chosen element at or before that index, every permutation has exactly a 1/n! probability of occurring. That is the Fisher-Yates shuffle, also called the Knuth shuffle.

The reason this works comes down to counting. At each step, you pick uniformly among the remaining unfinalized positions. The total number of ways to make those choices is n * (n-1) * (n-2) * ... * 1 = n!, and each sequence of choices leads to a unique permutation. So every permutation gets exactly one path through the decision tree.

The approach

1. Store a copy of the original array in the constructor so reset() can restore it
2. For shuffle(), iterate i from the last index down to 1
3. At each step, pick a random index j in the range [0, i]
4. Swap nums[i] with nums[j]
5. After the loop finishes, every element has been placed by a uniform random choice

The shuffle works in-place. No extra array needed beyond the original copy for reset.

The code

import random

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

    def reset(self):
        self.array = self.original[:]
        return self.array

    def shuffle(self):
        for i in range(len(self.array) - 1, 0, -1):
            j = random.randint(0, i)
            self.array[i], self.array[j] = self.array[j], self.array[i]
        return self.array

Notice how each step finalizes one position from right to left. Once an element has been swapped into its final slot, it never moves again. The unfinalized portion of the array shrinks by one each iteration until the entire array is shuffled.

Complexity

The shuffle itself is O(n) time and O(1) extra space since it works in-place. The constructor and reset each copy the array, which is O(n) time and space.

Building blocks

In-place swapping

The core mechanic is the in-place swap: nums[i], nums[j] = nums[j], nums[i]. This pattern shows up across array manipulation problems. Rather than allocating a new array and copying elements to their shuffled positions, you rearrange the existing array by swapping pairs of elements.

The Fisher-Yates shuffle is a specific application of this: each swap moves one element into its final position while keeping the rest available for future random selection. The same swap primitive appears in partition-based algorithms, sorting algorithms, and problems like Sort Colors or Move Zeroes.

Copy for reset

Storing self.original = nums[:] in the constructor is a common design pattern for problems that require resetting to an initial state. You need a separate copy because the shuffle modifies the array in-place. Without the copy, you would lose the original order permanently.

Why naive shuffles are biased

A common mistake is writing a loop where each element swaps with any random position in the full array:

# WRONG: biased shuffle
for i in range(len(nums)):
    j = random.randint(0, len(nums) - 1)
    nums[i], nums[j] = nums[j], nums[i]

This produces n^n possible swap sequences for an array of size n, but there are only n! permutations. Since n^n is not evenly divisible by n! for n > 2, some permutations must occur more often than others. The Fisher-Yates approach avoids this by restricting the random range at each step, producing exactly n! equally likely outcomes.

Edge cases

• Single element. An array of length 1 has only one permutation. The loop body never executes (the range is empty), and the array is returned unchanged.
• Two elements. The loop runs once with i = 1. You pick j as either 0 or 1, giving you a 50/50 chance of swapping or not. Both permutations are equally likely.
• All identical elements. The shuffle still runs and performs swaps, but every permutation looks the same. No special handling needed.
• Repeated shuffles. Each call to shuffle() operates on the current state of self.array, not on the original. If you want to shuffle the original each time, call reset() first.

From understanding to recall

The Fisher-Yates shuffle is one of those algorithms that is easy to get almost right but subtly wrong. The difference between a correct shuffle and a biased one is a single detail in the random range: randint(0, i) instead of randint(0, n-1).

The way to internalize it is to focus on the invariant. After processing index i, the elements at positions i through n-1 are finalized. The unshuffled portion is 0 through i-1. At each step, you pick one element from the unshuffled portion (including position i) and place it at position i by swapping. That mental model is easier to reconstruct under pressure than memorizing the exact loop bounds.

Write it from scratch. Trace through a small example by hand. Verify that the number of possible outcomes equals n!. Do that a few times over the course of a week and the algorithm becomes something you derive rather than recall.

Related posts

• Sort Colors - another in-place array rearrangement using swaps to partition elements
• Rotate Array - in-place array manipulation where pointer logic replaces extra memory
• Move Zeroes - swap-based array rearrangement with a read-write pointer pattern