LeetCode 384: Shuffle an Array

Problem Restatement

We are given an integer array nums.

We need to design a class with two operations:

The important requirement is that every possible permutation must be equally likely.

For an array of length n, there are n! possible permutations. A correct shuffle gives each one the same probability.

The problem guarantees that all elements in nums are unique. The array length is at least 1, and there may be many calls to reset() and shuffle().

Input and Output

Example class shape:

class Solution:

    def __init__(self, nums: list[int]):
        ...

    def reset(self) -> list[int]:
        ...

    def shuffle(self) -> list[int]:
        ...

Examples

Example:

solution = Solution([1, 2, 3])

Calling:

solution.shuffle()

may return:

[3, 1, 2]

Calling:

solution.reset()

returns:

[1, 2, 3]

Calling:

solution.shuffle()

may return another valid shuffle:

[1, 3, 2]

For [1, 2, 3], all six permutations should be equally likely:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Each one should have probability 1 / 6.

First Thought: Randomly Pick Until Empty

A simple way to shuffle is:

1. Put all numbers into a temporary list.
2. Randomly pick one number.
3. Remove it from the temporary list.
4. Repeat until no numbers remain.

This produces a random permutation, but removing from the middle of a Python list costs O(n).

So the full shuffle can become O(n^2).

We want a direct O(n) method.

Key Insight

Use the Fisher-Yates shuffle.

The idea is to fill the shuffled array one position at a time.

At index i, choose one random index j from the still-unfixed range:

i <= j < n

Then swap:

arr[i], arr[j] = arr[j], arr[i]

After this swap, position i is fixed.

Then move to i + 1.

This works because each position chooses uniformly among the remaining elements.

Algorithm

Store the original array:

self.original = nums[:]

For reset():

1. Return a copy of self.original.

For shuffle():

1. Make a copy of the original array.
2. For every index i from 0 to n - 1:
   • Pick random index j from i to n - 1.
   • Swap arr[i] and arr[j].
3. Return arr.

Correctness

At the first position, the algorithm chooses uniformly from all n elements.

So every element has probability 1 / n of being placed at index 0.

After index 0 is fixed, there are n - 1 remaining elements.

At index 1, the algorithm chooses uniformly from those remaining elements.

So each remaining element has probability 1 / (n - 1) of being placed at index 1, conditioned on the first choice.

This continues until every position is fixed.

For any specific permutation, the probability of producing it is:

(1 / n) * (1 / (n - 1)) * (1 / (n - 2)) * ... * (1 / 1)

That equals:

1 / n!

Since every permutation has the same probability, the shuffle is uniform.

The reset() method returns the saved original configuration, so it restores the array correctly.

Complexity

Let n = len(nums).

The extra O(n) space in shuffle() comes from returning a shuffled copy.

Implementation

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]:
        arr = self.original[:]
        n = len(arr)

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

        return arr

Code Explanation

We store a copy of the original input:

self.original = nums[:]

This protects the original order from future shuffle operations.

The reset() method returns a new copy:

return self.original[:]

Returning a copy is safer than returning the internal list directly, because external code should not mutate self.original.

For shuffling, we also start from a fresh copy:

arr = self.original[:]

Then we apply Fisher-Yates:

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

At each index i, we choose one of the remaining positions uniformly and swap it into place.

Finally:

return arr

Testing

Randomized code should not be tested by expecting one fixed shuffled output.

Instead, test structural properties:

def test_solution():
    nums = [1, 2, 3]
    s = Solution(nums)

    assert s.reset() == [1, 2, 3]

    shuffled = s.shuffle()
    assert sorted(shuffled) == [1, 2, 3]

    assert s.reset() == [1, 2, 3]

    single = Solution([42])
    assert single.shuffle() == [42]
    assert single.reset() == [42]

    nums2 = [-1, 0, 7, 9]
    s2 = Solution(nums2)

    for _ in range(100):
        shuffled = s2.shuffle()
        assert sorted(shuffled) == sorted(nums2)

    assert s2.reset() == nums2

    print("all tests passed")

test_solution()

Test meaning: