384. Shuffle an Array

Reformulated question¶

Design a class for an array that can:

return the original array with reset()
return a uniformly random permutation with shuffle()

Compact example:

nums = [1,2,3]
ops  = shuffle(), reset(), shuffle()
out  = any permutation of [1,2,3], [1,2,3], any permutation of [1,2,3]

Key trick¶

Use Fisher-Yates shuffle:

iterate every index i
swap a[i] with a random index j in [i, n - 1]

This makes every permutation equally likely.

Trap¶

Common mistakes:

only shuffling part of the array
picking random indices from the full range every time
mutating the stored original array
returning the same list object from reset() if later code may mutate it

Your current loop stops at n // 2, so it does not generate all permutations uniformly.

Why this question is interesting¶

It tests both:

API/state design with reset() vs current state
knowing the one correct uniform in-place shuffle algorithm

Pytest test¶

import pytest

@pytest.mark.parametrize(
    "nums",
    [
        [1],
        [1, 2],
        [1, 2, 3],
        [3, -1, 7, 9],
        [10, 20, 30, 40, 50],
    ],
)
def test_shuffle_array(nums):
    s = Solution(nums)

    assert s.reset() == nums
    assert s.reset() is not nums

    shuffled = s.shuffle()
    assert sorted(shuffled) == sorted(nums)
    assert len(shuffled) == len(nums)

    assert s.reset() == nums
    assert s.shuffle() is not s.reset()

Solve the problem with idiomatic Python¶

from random import randrange

class Solution:
    def __init__(self, nums: list[int]):
        # Keep an immutable reference copy of the original configuration.
        self.original = nums[:]

    def reset(self) -> list[int]:
        # Return a fresh copy so callers cannot mutate internal state.
        return self.original[:]

    def shuffle(self) -> list[int]:
        # Fisher-Yates shuffle: uniform over all permutations.
        arr = self.original[:]
        n = len(arr)
        for i in range(n):
            j = randrange(i, n)
            arr[i], arr[j] = arr[j], arr[i]
        return arr

Library alternative:

Python's random.shuffle solves this exact problem in \(O(n)\) too.

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[:]
        random.shuffle(arr)
        return arr

Comment my solution¶

Issues:

self.nums = nums
stores the caller's list directly, so outside mutation can change your internal state
reset() returns self.nums
returns the same object, not a safe copy
for i in range(nums_len // 2)
only shuffles half the positions, so distribution is wrong
your comment about picked elements never moving back
that is not enough; every index must be processed for uniformity

Minimal fix:

store nums[:]
return self.original[:]
loop over all indices with random j in [i, n - 1]

from random import randint

class Solution:

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


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


    def shuffle(self) -> list[int]:
        nums_len = len(self.nums)
        nums_shuffle = self.nums[:]
        for i in range(nums_len // 2):
            # swap elements at i and j
            # Since i is moving forward and we pick a element only
            # at indice superior to i, nums_shuffle[i] is never put
            # back to an earlier position
            j = randint(i, nums_len - 1)
            nums_shuffle[i], nums_shuffle[j] = nums_shuffle[j], nums_shuffle[i]

        return nums_shuffle

obj = Solution([1, 2, 3, 4])
obj.reset() # [1, 2, 3, 4]
obj.shuffle() # [4, 1, 3, 2]

Code¶

from random import randrange
import random
import pytest


class Solution:
    def __init__(self, nums: list[int]):
        # Preserve the initial configuration.
        self.original = nums[:]

    def reset(self) -> list[int]:
        # Return a copy so callers cannot mutate internal state.
        return self.original[:]

    def shuffle(self) -> list[int]:
        # Fisher-Yates shuffle: each permutation is equally likely.
        arr = self.original[:]
        n = len(arr)
        for i in range(n):
            j = randrange(i, n)
            arr[i], arr[j] = arr[j], arr[i]
        return arr


class SolutionWithLibrary:
    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[:]
        random.shuffle(arr)
        return arr


@pytest.mark.parametrize(
    "nums",
    [
        [1],
        [1, 2],
        [1, 2, 3],
        [3, -1, 7, 9],
        [10, 20, 30, 40, 50],
    ],
)
def test_shuffle_array(nums):
    s = Solution(nums)

    # reset returns original values
    assert s.reset() == nums

    # reset returns a new list, not the caller's exact object
    assert s.reset() is not nums

    # shuffle preserves elements
    shuffled = s.shuffle()
    assert sorted(shuffled) == sorted(nums)
    assert len(shuffled) == len(nums)

    # reset still restores original configuration
    assert s.reset() == nums

    # returned lists are fresh copies
    assert s.shuffle() is not s.reset()


s = Solution([1, 2, 3, 4])
s.reset()
s.shuffle()
s.reset()

slib = SolutionWithLibrary([1, 2, 3, 4])
slib.shuffle()
slib.reset()