Code Implementation

import random

class Solution:

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

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

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

#include <vector>
#include <cstdlib>
#include <ctime>

class Solution {
    std::vector<int> original;
    std::vector<int> array;
public:
    Solution(std::vector<int>& nums) {
        original = nums;
        array = nums;
        std::srand(std::time(nullptr));
    }
    
    std::vector<int> reset() {
        array = original;
        return array;
    }
    
    std::vector<int> shuffle() {
        for (int i = array.size() - 1; i > 0; --i) {
            int j = std::rand() % (i + 1);
            std::swap(array[i], array[j]);
        }
        return array;
    }
};
      

import java.util.Random;

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

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

class Solution {
    constructor(nums) {
        this.original = nums.slice();
        this.array = nums.slice();
    }
    
    reset() {
        this.array = this.original.slice();
        return this.array;
    }
    
    shuffle() {
        for (let i = this.array.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
        }
        return this.array;
    }
}
      

Problem Description

You are given an integer array nums. You need to design a class with the following capabilities:

• Solution(nums): Initializes the object with the array nums.
• reset(): Returns the array to its original configuration (as it was at initialization).
• shuffle(): Returns a random shuffling of the array. Each permutation of the array must be equally likely (i.e., uniform randomness).

Constraints:

• All elements must be used exactly once in the shuffled result (no repeats or omissions).
• Each possible permutation should be equally likely to occur.
• Multiple calls to shuffle() and reset() may be made.

Thought Process

At first glance, shuffling an array might seem as simple as randomly picking elements and rearranging them. However, ensuring that every possible permutation is equally likely (uniform randomness) is a key challenge. A naive approach might involve repeatedly picking random indices and moving elements, but this can lead to biased results where some permutations are more likely than others.

To solve this properly, we need an algorithm that guarantees each arrangement is equally probable. The Fisher-Yates (or Knuth) shuffle is a well-known algorithm that achieves this. It works by iterating through the array and swapping each element with another randomly chosen element that hasn't been shuffled yet.

Additionally, we need to allow resetting the array to its original state efficiently, which means we must store a copy of the initial array and avoid modifying it during shuffling.

Solution Approach

We use the Fisher-Yates shuffle algorithm for unbiased shuffling and simple array copying for reset functionality. Here are the steps:

1. Initialization:
   • Store a copy of the original array (original) for reset.
   • Use another array (array) for shuffling operations.
2. Reset:
   • Simply return a copy of the original array, restoring the initial configuration.
3. Shuffle (Fisher-Yates):
   • Iterate from the last index of array down to the first.
   • For each index i, pick a random index j between 0 and i (inclusive).
   • Swap array[i] and array[j].
   • This ensures that every element has an equal chance to end up in any position, resulting in all permutations being equally likely.
4. Why this works:
   • Each position is filled by a random element that hasn’t been placed yet, avoiding bias.
   • Reset is efficient because we just copy the original array.

Example Walkthrough

Let's consider nums = [1, 2, 3].

1. Initialization:
   • original = [1, 2, 3]
   • array = [1, 2, 3]
2. First shuffle:
   • Start at i = 2 (last index). Pick j randomly between 0 and 2.
   • Suppose j = 1. Swap array[2] and array[1]: [1, 3, 2]
   • Next, i = 1. Pick j randomly between 0 and 1.
   • Suppose j = 0. Swap array[1] and array[0]: [3, 1, 2]
   • Shuffle result: [3, 1, 2]
3. Reset:
   • Return original: [1, 2, 3]
4. Another shuffle:
   • Repeat the shuffle steps; the result could be any permutation, e.g., [2, 3, 1], [1, 3, 2], etc.

This process ensures that every permutation is possible and equally likely.

Time and Space Complexity

• Brute-force approach:
  • If we tried to generate all possible permutations and randomly pick one, it would take O(n!) time and space, which is infeasible for large arrays.
• Optimized Fisher-Yates shuffle:
  • Time Complexity: O(n) per shuffle, since we perform a constant-time swap for each element.
  • Space Complexity: O(n), as we store two arrays of size n (original and current).
  • Reset: Also O(n), since we copy the original array.

The optimized approach is efficient and scalable, making it suitable for large arrays.

Summary

The "Shuffle an Array" problem is elegantly solved by using the Fisher-Yates shuffle, which guarantees uniform randomness and efficiency. By keeping a copy of the original array, we can support quick resets. This approach is both simple and powerful, providing O(n) time complexity for shuffling and resetting, and ensuring every permutation is equally likely. The key insight is to use a proven algorithm (Fisher-Yates) rather than a naive or ad-hoc method, ensuring correctness and performance.