384. Shuffle an Array

Problem¶

Design a class for an array that can:

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

class Solution:
    def __init__(self, nums: list[int]):
        pass

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

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

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 is it interesting?¶

It tests both:

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

Python solution¶

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]:
        # Fisher-Yates shuffle: uniform over all permutations.
        arr = self.original[:]
        n = len(arr)
        for i in range(n):
            j = random.randrange(i, n)
            arr[i], arr[j] = arr[j], arr[i]
        return arr

Comment on 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]