LeetCode 384: Shuffle an Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 384: Shuffle an Array?

LeetCode 384: Shuffle an Array provides an integer array, and your task is to implement a Solution class that can shuffle the array into a random permutation (each possible permutation equally likely) and reset it to its original configuration. The problem tests your ability to design a system for efficient and unbiased shuffling!

Problem Statement

• Class: Solution
• Methods:
• __init__(nums): Initialize with the input array.
• reset(): Reset to the original array, return it.
• shuffle(): Return a random permutation of the array.
• Rules:
• Each permutation must have equal probability (1/n!).
• Original array must be preserved for reset.

Constraints

• 1 <= nums.length <= 50
• -10⁶ <= nums[i] <= 10⁶
• All elements in nums are unique.
• At most 10⁴ calls to reset and shuffle.

Examples

• Input: ["Solution","shuffle","reset","shuffle"], [[[1,2,3]],[],[],[]]
• Output: [null,[3,1,2],[1,2,3],[2,3,1]]
• Init: [1,2,3].
• shuffle(): e.g., [3,1,2] (any permutation).
• reset(): [1,2,3].
• shuffle(): e.g., [2,3,1] (another permutation).
• Input: ["Solution","reset","shuffle"], [[[1]],[],[]]
• Output: [null,[1],[1]]
• Init: [1], reset: [1], shuffle: [1] (only one permutation).

These show the shuffle dance—let’s solve it!

Understanding the Problem: Shuffling with Uniformity

To tackle LeetCode 384 in Python, we need a class that: 1. Initializes with an array and preserves its original state. 2. Shuffles the array into a random permutation with equal probability (1/n!). 3. Resets to the original array efficiently.

A naive approach might pick random indices, but ensuring uniformity is tricky. We’ll use:

• Best Solution: Fisher-Yates shuffle—O(n) time, O(n) space—fast and unbiased.
• Alternative Solution: Random selection with set—O(n) time, O(n) space—intuitive but less elegant.

Let’s shuffle with the best solution!

Best Solution: Fisher-Yates Shuffle

Why This Is the Best Solution

The Fisher-Yates (or Knuth) shuffle approach runs in O(n) time with O(n) space by iterating through the array once and randomly swapping each element with one from the remaining unprocessed portion. It’s the gold standard—guaranteeing uniform distribution (each permutation has 1/n! probability) while being simple and efficient!

How It Works

Think of it like shuffling a deck of cards:

• Copy: Store original array, work on a copy for shuffling.
• Shuffle: For each position i from 0 to n-1:
• Pick a random index j from i to n-1.
• Swap elements at i and j.
• Reset: Return the original copy.
• Result: Shuffled array or original as needed.

It’s like mixing cards one by one—perfectly random!

Step-by-Step Example

For nums = [1,2,3]:

• Init: Original = [1,2,3], Current = [1,2,3].
• shuffle():
• i=0: j = random[0,2], e.g., 2, swap: [3,2,1].
• i=1: j = random[1,2], e.g., 1, no swap: [3,2,1].
• i=2: Only 1 left, done.
• Result: [3,2,1] (1/6 chance, uniform).
• reset(): Return [1,2,3].
• shuffle():
• i=0: j=1, swap: [2,1,3].
• i=1: j=2, swap: [2,3,1].
• Result: [2,3,1] (1/6 chance).

For nums = [1]:

• Init: Original = [1], Current = [1].
• shuffle(): i=0, j=0, [1].
• reset(): [1].

Code with Explanation

Here’s the Python code using Fisher-Yates shuffle:

Copy codeimport random

class Solution:
    def __init__(self, nums: List[int]):
        # Store original and working copy
        self.original = nums[:]
        self.current = nums[:]

    def reset(self) -> List[int]:
        # Reset to original array
        self.current = self.original[:]
        return self.current

    def shuffle(self) -> List[int]:
        # Fisher-Yates shuffle
        n = len(self.current)
        for i in range(n):
            j = random.randint(i, n - 1)
            self.current[i], self.current[j] = self.current[j], self.current[i]
        return self.current

Explanation

• Lines 5-7: __init__:
• original: Copy of input nums for reset.
• current: Working copy for shuffling—O(n).
• Lines 9-12: reset:
• Copy original to current, return—O(n).
• Lines 14-19: shuffle:
• For each i, pick random j from i to n-1, swap—O(n).
• Each permutation has 1/n! probability.
• Time: O(n) for shuffle and reset.
• Space: O(n)—two arrays.

This is like a card shuffler—fast and fair!

Alternative Solution: Random Selection with Set

Why an Alternative Approach?

The random selection with set solution also runs in O(n) time for shuffle but uses O(n) space by picking elements randomly into a new list, ensuring no repeats with a set. It’s less efficient—great for understanding a selection-based approach, though it’s less elegant than Fisher-Yates!

How It Works

• Copy: Store original array.
• Shuffle:
• Use set to track picked indices.
• Randomly select n indices, build new array.
• Reset: Return original copy.

Step-by-Step Example

For nums = [1,2,3]:

• Init: Original = [1,2,3], Set = {}.
• shuffle():
• Pick random [0,2], e.g., 1, Set = {1}, Result = [2].
• Pick [0,2] - {1}, e.g., 0, Set = {1,0}, Result = [2,1].
• Pick 2, Set = {1,0,2}, Result = [2,1,3].
• reset(): [1,2,3].

Code with Explanation

Copy codeimport 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]:
        n = len(self.original)
        result = [0] * n
        used = set()

        for i in range(n):
            while True:
                idx = random.randint(0, n - 1)
                if idx not in used:
                    used.add(idx)
                    result[i] = self.original[idx]
                    break
        return result

Explanation

• Line 5: __init__: Store original array—O(n).
• Lines 7-8: reset: Return original—O(1) (reference).
• Lines 10-20: shuffle:
• Create result array, track used indices.
• For each position, pick random unused index—O(n) average.
• Time: O(n) shuffle (with retries), O(1) reset.
• Space: O(n)—result and set.

It’s a random picker—works but less clean!

Comparing the Two Solutions

• Fisher-Yates (Best):
• Time: O(n) shuffle/reset—linear.
• Space: O(n)—two arrays.
• Pros: Fast, uniform, in-place shuffle.
• Cons: Requires swap logic.
• Random Selection with Set (Alternative):
• Time: O(n) shuffle—linear with retries.
• Space: O(n)—extra set and array.
• Pros: Intuitive selection.
• Cons: More space, retries possible.

Fisher-Yates wins for elegance and efficiency!

Additional Examples and Edge Cases

• [1]: Both return [1] on shuffle.
• [1,2]: Both permute uniformly (1/2 chance each).
• Large n: Fisher-Yates scales cleanly.

Both work, Fisher-Yates is superior.

Complexity Breakdown

• Fisher-Yates:
• Time: O(n) shuffle/reset.
• Space: O(n).
• Random Selection:
• Time: O(n) shuffle, O(1) reset.
• Space: O(n).

Fisher-Yates excels for uniformity and simplicity.

Key Takeaways

• Fisher-Yates: Shuffle in place—fast and fair!
• Random Selection: Pick and place—clear but clunky!
• Randomness: Uniformity is key.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Shuffle That Array

LeetCode 384: Shuffle an Array in Python is a randomization challenge. Fisher-Yates is the efficiency champ, while random selection with set offers a simpler but less optimal alternative. Want more? Try LeetCode 380: Insert Delete GetRandom O(1) or LeetCode 398: Random Pick Index. Ready to mix? Visit Solve LeetCode 384 on LeetCode and shuffle that array today!