Skip to main content
Back to Library
cracking the tech interview system design and algorithms in java 25

Fisher-Yates Shuffle

10 min read Chapter 75 of 75
Summary

Covers the Fisher-Yates (Knuth) shuffle algorithm, proof of...

Covers the Fisher-Yates (Knuth) shuffle algorithm, proof of uniform distribution, common mistakes that produce biased shuffles, and applications in sampling and randomization.

Fisher-Yates Shuffle

Shuffling an array sounds trivial. It isn’t. Most intuitive approaches produce biased results — some permutations appear more often than others. The Fisher-Yates shuffle generates a uniformly random permutation where each of the n! arrangements is equally likely, and it does so in O(n) time with O(1) extra space. Let’s understand exactly how and why it works.

The Problem

Given an array of n elements, rearrange them so that every possible permutation has equal probability 1/n! of being produced.

Naive Approach: Sort by Random Keys

Assign each element a random key, then sort by those keys:

void naiveShuffle(int[] arr) {
    var rng = ThreadLocalRandom.current();
    Integer[] indices = new Integer[arr.length];
    double[] keys = new double[arr.length];
    for (int i = 0; i < arr.length; i++) {
        indices[i] = i;
        keys[i] = rng.nextDouble();
    }
    Arrays.sort(indices, (a, b) -> Double.compare(keys[a], keys[b]));

    int[] copy = arr.clone();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = copy[indices[i]];
    }
}

This works — with continuous random keys, ties have probability zero, and all orderings are equally likely. But it costs O(n log n) for the sort, uses O(n) extra space, and is far more complex than necessary.

Fisher-Yates (Knuth) Shuffle

The classic algorithm iterates from the end of the array to the beginning. At each position i, it picks a random index j from [0, i] and swaps the elements at positions i and j.

void fisherYatesShuffle(int[] arr) {
    var rng = ThreadLocalRandom.current();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = rng.nextInt(i + 1); // random index in [0, i]
        // Swap arr[i] and arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Three lines of logic. O(n) time. O(1) extra space. Each element gets placed exactly once.

Forward Variant (Durstenfeld)

The algorithm works equally well iterating forward. At each position i, pick a random index j from [i, n-1]:

void forwardShuffle(int[] arr) {
    var rng = ThreadLocalRandom.current();
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int j = i + rng.nextInt(n - i); // random index in [i, n-1]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Both variants produce identical distributions. The backward version is the traditional formulation; the forward version is sometimes more intuitive.

Proof of Uniformity

Why does every permutation have equal probability? Let’s trace through the math for an array of size n.

Position n-1 (first iteration of backward variant): element placed here is chosen uniformly from all n elements. Probability of any specific element landing here: 1/n.

Position n-2 (second iteration): element placed here is chosen uniformly from the remaining n-1 elements. Probability of a specific element reaching this position: it must NOT have been selected in step 1 (probability (n-1)/n), AND it must be selected now (probability 1/(n-1)).

$$P = \frac{n-1}{n} \times \frac{1}{n-1} = \frac{1}{n}$$

Position n-3: probability = must survive steps 1 and 2, then be selected:

$$P = \frac{n-1}{n} \times \frac{n-2}{n-1} \times \frac{1}{n-2} = \frac{1}{n}$$

By induction: every element has probability exactly 1/n of occupying any given position.

Total permutations: the algorithm makes n-1 independent random choices, producing n × (n-1) × (n-2) × … × 2 × 1 = n! equally likely outcomes. Since there are exactly n! permutations, each one has probability 1/n!.

The Common Mistake: Biased Shuffle

Here’s the shuffle that looks correct but produces biased results:

// WRONG — produces biased shuffle!
void biasedShuffle(int[] arr) {
    var rng = ThreadLocalRandom.current();
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        int j = rng.nextInt(n); // BUG: picks from [0, n-1] every time
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

The bug: j ranges over [0, n-1] at every iteration instead of shrinking the range.

Why it’s biased: this algorithm produces n^n equally likely execution paths (n choices at each of n iterations). But there are only n! permutations. Since n! does not evenly divide n^n for any n ≥ 3, the permutations cannot be uniformly distributed — some must receive more execution paths than others.

Concrete example for n = 3 (elements [1, 2, 3]):

The correct algorithm produces 3! = 6 execution paths → 6 permutations, each with probability 1/6.

The biased algorithm produces 3³ = 27 execution paths. Distributed among 6 permutations, each permutation “should” get 27/6 = 4.5 paths. But 4.5 isn’t an integer — so some permutations get 4 paths (probability 4/27) and others get 5 paths (probability 5/27). The distribution is measurably nonuniform.

Partial Shuffle: Selecting k Random Elements

Need k random elements from an array of size n, without replacement? Run Fisher-Yates for only k iterations:

int[] randomSample(int[] arr, int k) {
    var rng = ThreadLocalRandom.current();
    int n = arr.length;
    int[] copy = arr.clone(); // preserve original
    int[] sample = new int[k];

    for (int i = 0; i < k; i++) {
        int j = i + rng.nextInt(n - i);
        // Swap
        int temp = copy[i];
        copy[i] = copy[j];
        copy[j] = temp;
        sample[i] = copy[i];
    }
    return sample;
}

After k iterations, the first k positions contain a uniformly random sample. O(k) time — dramatically better than shuffling the entire array when k is much smaller than n.

The proof follows the same logic: each element has probability k/n of appearing in the sample, and all $\binom{n}{k}$ possible samples are equally likely.

Reservoir Sampling (Algorithm R)

Problem: select k items uniformly at random from a data stream of unknown length. You can’t store the entire stream — you have memory for only k items.

int[] reservoirSample(Iterator<Integer> stream, int k) {
    int[] reservoir = new int[k];

    // Fill reservoir with first k items
    for (int i = 0; i < k; i++) {
        reservoir[i] = stream.next();
    }

    // Process remaining items
    var rng = ThreadLocalRandom.current();
    int index = k;
    while (stream.hasNext()) {
        int item = stream.next();
        int j = rng.nextInt(index + 1); // random in [0, index]
        if (j < k) {
            reservoir[j] = item; // replace a random reservoir element
        }
        index++;
    }
    return reservoir;
}

How It Works

For each new item at position i (0-indexed), generate a random number j in [0, i]. If j < k, replace reservoir[j] with the new item. Otherwise, discard it.

Proof of Uniformity

After seeing n total items, each item should have probability k/n of being in the reservoir.

For the ith item (i ≥ k):

  • Probability of being selected: k/(i+1)
  • Probability of surviving all subsequent replacements: for each later item at position t, the probability of NOT being replaced is 1 - 1/(t+1) = t/(t+1)… but that calculation applies only if the new item targets our specific slot (probability 1/k).

Combining: probability that item i is in the final reservoir:

$$P = \frac{k}{i+1} \times \frac{i+1}{i+2} \times \frac{i+2}{i+3} \times \cdots \times \frac{n-1}{n} = \frac{k}{n}$$

The telescoping product collapses beautifully. Every item — whether it arrived first or last — has probability exactly k/n of being in the final reservoir.

Applications

  • Random line from a large file: reservoir with k = 1, stream through lines.
  • Sampling from data pipelines: process events without knowing the total count.
  • A/B testing: select random users from an incoming traffic stream.
  • Machine learning: random sampling from datasets too large for memory.

Shuffle-Based Interview Patterns

Shuffle an Array (LeetCode #384)

Design a class that can shuffle an array and reset it to its original configuration:

class ShuffleArray {
    private final int[] original;
    private int[] current;

    ShuffleArray(int[] nums) {
        this.original = nums.clone();
        this.current = nums.clone();
    }

    int[] reset() {
        current = original.clone();
        return current;
    }

    int[] shuffle() {
        var rng = ThreadLocalRandom.current();
        for (int i = current.length - 1; i > 0; i--) {
            int j = rng.nextInt(i + 1);
            int temp = current[i];
            current[i] = current[j];
            current[j] = temp;
        }
        return current;
    }
}

Random Pick with Weight

Given an array of weights, pick an index with probability proportional to its weight. Not a shuffle problem per se, but it shares the probabilistic reasoning:

class WeightedRandom {
    private final int[] prefixSums;
    private final int totalWeight;

    WeightedRandom(int[] weights) {
        prefixSums = new int[weights.length];
        prefixSums[0] = weights[0];
        for (int i = 1; i < weights.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + weights[i];
        }
        totalWeight = prefixSums[weights.length - 1];
    }

    int pickIndex() {
        int target = ThreadLocalRandom.current().nextInt(totalWeight) + 1;
        // Binary search for the first prefix sum >= target
        int lo = 0, hi = prefixSums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefixSums[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Java’s Built-in: Collections.shuffle()

Java’s Collections.shuffle(List<?> list) uses Fisher-Yates internally. Under the hood, it calls Collections.shuffle(list, new Random()), which implements the backward variant. For thread-safe applications, pass a ThreadLocalRandom explicitly:

var list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
Collections.shuffle(list, ThreadLocalRandom.current());

For arrays, there’s no built-in — write Fisher-Yates yourself.

Testing Randomness

How do you verify that your shuffle is truly uniform? Run it many times and apply a chi-squared test: for each position, count how often each element appears; the counts should be approximately equal. A significant deviation from the expected uniform distribution indicates bias.

void testUniformity(int n, int trials) {
    int[][] counts = new int[n][n]; // counts[pos][element]
    int[] arr = new int[n];

    for (int t = 0; t < trials; t++) {
        for (int i = 0; i < n; i++) arr[i] = i;
        fisherYatesShuffle(arr);
        for (int pos = 0; pos < n; pos++) {
            counts[pos][arr[pos]]++;
        }
    }

    double expected = (double) trials / n;
    double chiSquared = 0;
    for (int pos = 0; pos < n; pos++) {
        for (int elem = 0; elem < n; elem++) {
            double diff = counts[pos][elem] - expected;
            chiSquared += (diff * diff) / expected;
        }
    }
    System.out.printf("Chi-squared: %.2f (df=%d)%n", chiSquared, n * n - 1);
}

For large trial counts, the chi-squared statistic should be close to the degrees of freedom (n² - 1). A value far above indicates bias.

Interviewer Tips

Fisher-Yates demonstrates that you understand probability at a practical level. The three things interviewers look for:

  1. Correct range: rng.nextInt(i + 1) not rng.nextInt(n). This single detail separates uniform from biased.
  2. Proof of uniformity: articulate why each permutation has probability 1/n! — use the telescoping probability argument.
  3. Reservoir sampling connection: if the follow-up is “what if the data is streaming?”, pivot to Algorithm R with confidence.

The biased shuffle mistake is a favorite interview trap. If you can explain why n^n doesn’t divide evenly by n!, you’ve demonstrated the kind of mathematical reasoning that stands out.