384. Shuffle an Array

384

MediumRandomization, Math and Miscellaneous (FAANG add-on)In-place uniform random permutationFisher-Yates shuffle

Shuffle an Array

Design a class over an integer array that supports two operations: reset() restores and returns the array in its original order, and shuffle() returns a uniformly random permutation of the array in which every possible ordering is equally likely.

Open official problem prompt ↗

In plain English

Produce a random reordering of an array where all n! orderings are equally probable, plus the ability to snap back to the starting order.

Picture it like this

Shuffling a deck by repeatedly picking one card at random from the cards you have not yet placed and laying it down next — every card is equally likely to end up in any position.

Example

Input: operations = ["Solution", "shuffle", "reset", "shuffle"], args = [[[1,2,3]], [], [], []]
Output: [null, [3,1,2], [1,2,3], [3,2,1]]
Why: shuffle returns a random permutation of [1,2,3], reset restores the original [1,2,3], and the next shuffle produces another random permutation.

Constraints

1 <= nums.length <= 50-10^6 <= nums[i] <= 10^6All elements of nums are uniqueAt most 10^4 calls total to reset and shuffle

Pattern lesson

See the pattern, then code

Fisher-Yates shuffle

↗

Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. Walk left to right; at index i pick a random element from the still-unshuffled suffix [i, n-1] and swap it into position i. Each element lands in each slot with probability exactly 1/n, giving all n! permutations equal weight.

New words, made simpleKnow these before the algorithm

Uniform permutation: A shuffle where each of the n! orderings has probability 1/n!.
Fisher-Yates / Knuth shuffle: An O(n) algorithm that swaps each index with a random index from the remaining suffix.
Unbiased: No ordering is more likely than another; a naive random sort is often biased.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort by random keys

Slower, and ties or a biased comparator can skew the distribution.

Assign each element a random float and sort by it.

Time O(n log n)Space O(n)

Pick-and-remove into new list

Correct distribution but pops from the middle are O(n), giving quadratic time.

Repeatedly pop a random index from the source into a result list.

Time O(n^2)Space O(n)

Best choiceFisher-Yates in place

Linear, in place, and provably uniform — the standard answer.

For each i, swap arr[i] with arr[randint(i, n-1)].

Time O(n)Space O(1) beyond the stored original

The rule we keep true

Invariant

After processing index i, positions 0..i hold a uniformly random selection-without-replacement drawn from all elements, and the suffix i+1..n-1 still contains the untouched remainder.

Why this is correct

Reasoning

By induction: element chosen for slot 0 is uniform over all n; given that, slot 1 is uniform over the remaining n-1, and so on. Multiplying the per-step probabilities gives 1/(n·(n-1)···1) = 1/n! for every specific ordering.

The algorithm in three movesSay these aloud before coding

1Store a pristine copy of the original array for reset

i=0: j=randint(0,2)=2 -> swap -> [3,2,1]

2For shuffle, iterate i from 0 to n-1

i=1: j=randint(1,2)=2 -> swap -> [3,1,2]

3At each i draw a random j in [i, n-1] and swap arr[i] with arr[j]

i=2: j=2 -> no-op -> [3,1,2]

4Return the shuffled working array; reset copies the original back

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnums = [1,2,3]

2 · AskWhat must be preserved?

3 · Update stateoriginal = [1,2,3], arr = [1,2,3]

4 · ResultWorking copy ready

Key takeaway

Fisher-Yates swaps position 0 with a random later slot, then narrows the range each step.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Store original
Keep an immutable copy so reset can restore the initial order at any time.
2
Lines 8-10reset
Copy the original back over the working array so subsequent shuffles start clean.
3
Lines 12-18shuffle
The Fisher-Yates loop: each slot receives a random element from the untouched suffix.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-element array — shuffle returns it unchanged
Repeated shuffle calls must each be independent and unbiased
reset must return the exact original order even after many shuffles

Common beginner mistakes

Choosing j from [0, n-1] instead of [i, n-1] — this over-samples and is biased (Sattolo-like error)
Returning a shared reference so the caller mutates internal state — copy on init
Forgetting to keep a separate original, so reset cannot recover the starting order

Check your understanding

Why must the random index j be drawn from [i, n-1] rather than [0, n-1]?

Shuffle an Array

Shuffle an Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Randomization, Math and Miscellaneous (FAANG add-on)