#384

Medium

LeetCode Problem Workspace

Shuffle an Array

Shuffle an Array requires designing a class to randomly permute an integer array while ensuring all permutations are equally likely.

array math design randomized

Problem Statement

Design a class that takes an integer array and allows it to be shuffled randomly. Every permutation of the array must be equally likely when shuffled, and the class should also support resetting to the original configuration.

Implement the Solution class with two main functions: shuffle, which returns a randomly shuffled array ensuring uniform probability, and reset, which restores the array to its original order. Optimize the approach to handle multiple calls efficiently under the problem constraints.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []] Output [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // Shuffle the array [1,2,3] and return its result. // Any permutation of [1,2,3] must be equally likely to be returned. // Example: return [3, 1, 2] solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3] solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Constraints

1 <= nums.length <= 50
-106 <= nums[i] <= 106
All the elements of nums are unique.
At most 104 calls in total will be made to reset and shuffle.

Solution Approach

Store Original Array

Keep a copy of the input array in the constructor to use for reset and to ensure each shuffle starts from the original configuration, preventing cumulative bias.

Fisher-Yates Shuffle

Implement the Fisher-Yates algorithm by iterating from the end of the array and swapping each element with a randomly chosen element from the portion not yet shuffled. This ensures all permutations are equally likely.

Handle Multiple Calls Efficiently

Each shuffle or reset call should operate in O(n) time, with O(n) additional space for the copy of the original array. This guarantees performance even for repeated operations under the problem constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity for shuffle is O(n) per call, and reset is O(n) for copying. Space complexity is O(n) for storing the original array copy, ensuring repeated shuffles do not accumulate errors.

What Interviewers Usually Probe

Asks about unbiased shuffling of arrays.
Checks if Fisher-Yates is implemented correctly to ensure uniform permutations.
Verifies handling multiple shuffle and reset calls efficiently.

Common Pitfalls or Variants

Common pitfalls

Modifying the array in place without preserving the original leads to biased shuffles.
Using naive random swaps can produce non-uniform distributions.
Failing to handle multiple consecutive shuffle calls from the same modified array.

Follow-up variants

Shuffle a linked list maintaining equal probability for all node permutations.
Shuffle a multidimensional array along one axis uniformly.
Implement a weighted shuffle where each element has a different selection probability.

FAQ

What is the main idea behind Shuffle an Array?

The main idea is to create a Solution class that can shuffle an array randomly while allowing it to be reset to its original order.

Why is Fisher-Yates recommended for this problem?

Fisher-Yates guarantees each permutation of the array occurs with equal probability, avoiding bias that arises from naive shuffling methods.

How should multiple shuffle calls be handled?

Always start shuffle from a copy of the original array to ensure uniform randomness across repeated calls, preventing cumulative bias.

Can this approach work for arrays with negative numbers?

Yes, the algorithm works for any integer values within the array, as randomness is independent of the numeric values.

What pattern does this problem demonstrate?

It exemplifies the Array plus Math pattern, combining array manipulation with probability principles to ensure unbiased permutations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

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

    def shuffle(self) -> List[int]:
        for i in range(len(self.nums)):
            j = random.randrange(i, len(self.nums))
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums


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

Continue Practicing

#381 insert delete getrandom o1 duplicates allowed #380 insert delete getrandom o1 #497 random point in non overlapping rectangles