384. Shuffle an Array

Description

The problem involves designing a class that can shuffle an array of integers and reset it to its original state. The class should support two main operations:

1. reset() - Resets the array to its original configuration and returns it.
2. shuffle() - Returns a random shuffling of the array.

The challenge is to shuffle the array in a way that all permutations of the array are equally likely, simulating a fair shuffle.

Intuition

Shuffling an array requires a random and unbiased process to rearrange elements. The Fisher-Yates algorithm is a widely recognized method for generating random permutations, which ensures that each possible permutation of the array is equally likely. For resetting, we simply store a copy of the original array and restore it when needed.

Approach

1. Initialization: In the constructor, store both the original array and the working array (which will be shuffled).
2. Reset: Simply return the original array, or copy it to avoid altering it.
3. Shuffle: - Use the Fisher-Yates algorithm: Traverse the array from the last index to the first. For each element, swap it with another randomly chosen element that comes before it (or itself). - This ensures that every permutation has an equal probability of being selected.

Complexity

Time Complexity:

• The constructor runs in O(n) where n is the number of elements in the array, as it copies the array.
• The reset() function also runs in O(n) since it returns a copy of the original array.
• The shuffle() function runs in O(n) as it iterates through the array once and performs constant-time operations for each element.

Space Complexity:

• The space complexity is O(n) due to the need to store both the original array and the shuffled array.

Code

C++

class Solution {
private:
    std::vector nums;
    std::vector original;
    
public:
    Solution(std::vector& nums) : nums(nums), original(nums) {}
    
    std::vector reset() {
        nums = original;  // Restore to the original array
        return nums;
    }
    
    std::vector shuffle() {
        std::vector shuffled = nums;
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(shuffled.begin(), shuffled.end(), g);
        return shuffled;
    }
};

Python

class Solution:

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

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

    def shuffle(self) -> list[int]:
        shuffled = self.nums[:]
        for i in range(len(shuffled) - 1, 0, -1):
            j = random.randint(0, i)
            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
        return shuffled

Java

class Solution {
    private int[] nums;
    private int[] original;
    private Random rand = new Random();

    public Solution(int[] nums) {
        this.nums = nums;
        this.original = nums.clone();
    }

    public int[] reset() {
        nums = original.clone();  // Reset to the original array
        return nums;
    }

    public int[] shuffle() {
        int[] shuffled = nums.clone();
        for (int i = shuffled.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int temp = shuffled[i];
            shuffled[i] = shuffled[j];
            shuffled[j] = temp;
        }
        return shuffled;
    }
}

JavaScript

/**
 * @param {number[]} nums
 */
var Solution = function (nums) {
    this.nums = nums;
    this.original = nums.slice();
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function () {
    return this.original;
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function () {
    const shuffled = this.nums.slice();
    for (let i = shuffled.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
    }
    return shuffled;
};