LeetCode 384 - Shuffle an Array

Difficulty: 🟡 Medium
Topics: Array, Math, Design, Randomized

Solution

Problem Understanding

The problem asks us to design a data structure that supports two operations on an integer array:

Reset the array back to its original order.
Return a randomly shuffled version of the array.

The important requirement is that every possible permutation of the array must be equally likely. This means the shuffle operation cannot introduce statistical bias. If the array contains n elements, there are n! possible permutations, and each one must occur with probability 1 / n!.

The constructor receives the initial array and stores it internally. The reset() method must restore and return the original configuration exactly as it was when the object was created. The shuffle() method must return a randomly permuted version of the array.

The constraints are relatively small:

1 <= nums.length <= 50
All elements are unique
At most 10^4 total calls to reset and shuffle

Although the array size is small, the problem is fundamentally about correctness of randomization rather than raw performance. A naive implementation might appear to work visually while still producing biased permutations.

Because all elements are unique, we do not need to worry about duplicate values creating indistinguishable permutations. This simplifies the probability analysis.

Several edge cases are important:

Arrays of length 1, where shuffling should always return the same array.
Multiple consecutive calls to shuffle(), which must remain independent and unbiased.
Calls to reset() after shuffling, which must restore the exact original order.
Avoiding accidental mutation of the stored original array.

Approaches

Brute Force Approach

A brute force approach is to generate all possible permutations of the array, store them in a list, and then randomly select one permutation whenever shuffle() is called.

This approach is correct because every permutation is explicitly generated, so choosing uniformly from the list guarantees equal probability for all outcomes.

However, the number of permutations grows factorially. An array of length n has n! permutations. Even though the constraints are small, factorial growth becomes impractical very quickly. For example:

5! = 120
10! = 3,628,800
50! is astronomically large

Both memory usage and preprocessing time become completely infeasible.

Optimal Approach

The optimal solution uses the Fisher-Yates Shuffle algorithm, also called the Knuth Shuffle.

The key insight is that instead of generating every permutation, we can build a uniformly random permutation incrementally.

At each position in the array, we randomly choose one of the remaining unused elements and place it there. By ensuring that every remaining element has equal probability of being selected at each step, all final permutations become equally likely.

The Fisher-Yates algorithm works in-place and runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generates every permutation explicitly
Optimal	O(n)	O(n)	Uses Fisher-Yates shuffle with uniform randomness

Algorithm Walkthrough

Fisher-Yates Shuffle

Store a copy of the original array during initialization.

We need the original configuration so that reset() can restore it later. A copy is necessary because the shuffled array will be modified in-place. 2. In reset(), return a fresh copy of the original array.

Returning the original reference directly is dangerous because external code could modify it. Returning a copy prevents accidental mutation. 3. In shuffle(), create a working copy of the original array.

We do not want to permanently alter the stored original configuration. 4. Iterate through the array from left to right.

Suppose we are currently at index i. 5. Randomly choose an index j between i and n - 1.

This range represents all elements that have not yet been fixed into their final positions. 6. Swap the elements at indices i and j.

This places one randomly selected remaining element into position i. 7. Continue until every position has been processed.

After the final iteration, the array is fully shuffled.

Why it works

The correctness comes from the fact that each position chooses uniformly among all remaining unused elements.

For an array of size n:

The first position has n equally likely choices.
The second position has n - 1 equally likely choices.
The third position has n - 2 equally likely choices.

Continuing this process produces exactly:

$n \times (n-1) \times (n-2) \times \cdots \times 1 = n!$

possible outcomes, and every permutation is generated with equal probability.

Python Solution

from typing import List
import random

class Solution:

    def __init__(self, nums: List[int]):
        self.original = nums[:]

    def reset(self) -> List[int]:
        return self.original[:]

    def shuffle(self) -> List[int]:
        shuffled = self.original[:]
        n = len(shuffled)

        for i in range(n):
            j = random.randint(i, n - 1)
            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]

        return shuffled

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

The constructor stores a copy of the input array in self.original. Using slicing creates a separate list so later modifications do not affect the stored version.

The reset() method simply returns a fresh copy of the original array. Returning a copy instead of the internal reference prevents callers from mutating internal state.

The shuffle() method creates another copy called shuffled. This is the array we will modify.

The loop processes each index i. For every position, we randomly choose an index j from the range [i, n - 1]. Swapping these values guarantees that every remaining element has equal probability of occupying position i.

The algorithm modifies the array in-place and finishes in linear time.

Go Solution

package main

import (
	"math/rand"
)

type Solution struct {
	original []int
}

func Constructor(nums []int) Solution {
	originalCopy := make([]int, len(nums))
	copy(originalCopy, nums)

	return Solution{
		original: originalCopy,
	}
}

func (this *Solution) Reset() []int {
	resetCopy := make([]int, len(this.original))
	copy(resetCopy, this.original)

	return resetCopy
}

func (this *Solution) Shuffle() []int {
	shuffled := make([]int, len(this.original))
	copy(shuffled, this.original)

	n := len(shuffled)

	for i := 0; i < n; i++ {
		j := rand.Intn(n-i) + i
		shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
	}

	return shuffled
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */

The Go implementation follows the same logic as the Python version, but slices require careful copying because slices reference shared underlying arrays.

The copy() function is used whenever we need an independent slice. Without copying, mutations during shuffling would alter the stored original array.

The random index generation differs slightly from Python. rand.Intn(k) generates a value in [0, k), so we shift it by i to obtain the range [i, n - 1].

Integer overflow is not a concern because the constraints are very small.

Worked Examples

Example 1

Input array:

[1, 2, 3]

Initialization

Variable	Value
original	[1, 2, 3]

First shuffle()

Suppose the random choices are:

i = 0, choose j = 2
i = 1, choose j = 1
i = 2, choose j = 2

Initial working array:

Step	i	j	Array State
Start	-	-	[1, 2, 3]
Swap indices 0 and 2	0	2	[3, 2, 1]
Swap indices 1 and 1	1	1	[3, 2, 1]
Swap indices 2 and 2	2	2	[3, 2, 1]

Returned result:

[3, 2, 1]

reset()

The stored original array remains unchanged.

Variable	Value
original	[1, 2, 3]

Returned result:

[1, 2, 3]

Second shuffle()

Suppose the random choices are:

i = 0, choose j = 0
i = 1, choose j = 2
i = 2, choose j = 2

Step	i	j	Array State
Start	-	-	[1, 2, 3]
Swap indices 0 and 0	0	0	[1, 2, 3]
Swap indices 1 and 2	1	2	[1, 3, 2]
Swap indices 2 and 2	2	2	[1, 3, 2]

Returned result:

[1, 3, 2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once during shuffling
Space	O(n)	A copy of the array is created for reset and shuffle operations

The Fisher-Yates algorithm performs a single pass through the array. Every iteration executes constant-time work consisting of random number generation and a swap.

Additional space is required because we preserve the original array and create working copies during operations.

Test Cases

from typing import List
import random

class Solution:

    def __init__(self, nums: List[int]):
        self.original = nums[:]

    def reset(self) -> List[int]:
        return self.original[:]

    def shuffle(self) -> List[int]:
        shuffled = self.original[:]

        for i in range(len(shuffled)):
            j = random.randint(i, len(shuffled) - 1)
            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]

        return shuffled

# Test 1: basic example from prompt
obj = Solution([1, 2, 3])
shuffled = obj.shuffle()
assert sorted(shuffled) == [1, 2, 3]  # shuffled array contains same elements
assert obj.reset() == [1, 2, 3]  # reset restores original order

# Test 2: single element array
obj = Solution([5])
assert obj.shuffle() == [5]  # only one possible permutation
assert obj.reset() == [5]  # reset still works

# Test 3: negative numbers
obj = Solution([-1, -2, -3])
shuffled = obj.shuffle()
assert sorted(shuffled) == [-3, -2, -1]  # preserves all elements

# Test 4: multiple shuffles
obj = Solution([1, 2, 3, 4])
shuffle1 = obj.shuffle()
shuffle2 = obj.shuffle()
assert sorted(shuffle1) == [1, 2, 3, 4]  # first shuffle valid
assert sorted(shuffle2) == [1, 2, 3, 4]  # second shuffle valid

# Test 5: reset after shuffle
obj = Solution([10, 20, 30])
obj.shuffle()
assert obj.reset() == [10, 20, 30]  # reset restores original

# Test 6: ensure reset returns copy
obj = Solution([1, 2, 3])
arr = obj.reset()
arr[0] = 999
assert obj.reset() == [1, 2, 3]  # internal state unaffected

# Test 7: larger array
nums = list(range(50))
obj = Solution(nums)
shuffled = obj.shuffle()
assert sorted(shuffled) == nums  # all elements preserved

# Test 8: repeated resets
obj = Solution([7, 8, 9])
assert obj.reset() == [7, 8, 9]  # first reset
assert obj.reset() == [7, 8, 9]  # second reset

print("All tests passed!")

Test	Why
`[1,2,3]` example	Validates standard functionality
Single element array	Ensures trivial case behaves correctly
Negative numbers	Confirms values themselves do not matter
Multiple shuffles	Verifies repeated calls remain valid
Reset after shuffle	Ensures original configuration is preserved
Reset returns copy	Prevents accidental external mutation
Array of length 50	Tests upper constraint boundary
Repeated resets	Confirms reset is stable across calls

Edge Cases

Single Element Array

An array containing only one element has exactly one possible permutation. A naive implementation might still attempt unnecessary swaps or random operations. The Fisher-Yates algorithm handles this naturally because the loop either runs once with a self-swap or performs no meaningful change.

External Mutation of Returned Arrays

One subtle bug occurs when returning direct references to internal arrays. If the caller modifies the returned array, the internal state of the object can become corrupted. This implementation avoids the issue by always returning copies using slicing in Python and copy() in Go.

Multiple Consecutive Shuffle Calls

Some incorrect implementations shuffle the already shuffled array repeatedly. While this may appear acceptable, it complicates reasoning about correctness and can accidentally introduce bias if implemented poorly. This solution always starts from the original stored configuration before shuffling, ensuring every shuffle call independently produces a uniformly random permutation.