How to Shuffle an Array Uniformly in Java: Fisher‑Yates Solution Explained

Background

Recent news about companies offering voluntary layoffs with generous severance sparked a short reflection on why many professionals now prefer a clean exit when work becomes stressful and unrewarding.

Problem Statement

You are given an integer array nums and need to design a class that can:

Initialize with the array.

Reset the array to its original order via reset().

Return a random shuffling of the array via shuffle(), ensuring every possible permutation appears with equal probability.

Common Pitfall

A typical but incorrect solution swaps each element with a random index chosen from the whole array. This approach generates some permutations more often than others, so interviewers will quickly spot the bias.

Correct Solution – Fisher‑Yates Shuffle

The Fisher‑Yates algorithm guarantees a uniform random permutation:

Iterate the index i from the last element down to the second element.

For each i, pick a random index j in the range [0, i].

Swap nums[i] and nums[j].

Because each element is placed into a random remaining position exactly once, every permutation has the same probability.

Java Implementation

import java.util.Random;

public class Solution {
    private int[] original; // saved original array
    private int[] nums;     // working copy
    private Random random;

    public Solution(int[] nums) {
        this.original = nums.clone();
        this.nums = nums.clone();
        this.random = new Random();
    }

    // Restore the array to its original state
    public int[] reset() {
        System.arraycopy(original, 0, nums, 0, original.length);
        return nums;
    }

    // Perform Fisher‑Yates shuffle
    public int[] shuffle() {
        for (int i = nums.length - 1; i > 0; i--) {
            // pick a random index in [0, i]
            int j = random.nextInt(i + 1);
            swap(nums, i, j);
        }
        return nums;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

Key Points

Two clones are used: one to keep the immutable original for reset(), and another as the mutable working array. System.arraycopy (or simply nums = original.clone()) can be used to reset efficiently.

For random number generation, java.util.Random is sufficient; in high‑concurrency scenarios ThreadLocalRandom would be preferable.

The algorithm runs in O(n) time with O(1) extra space, which is optimal for interview expectations.