384. Shuffle an Array

MediumArrayMathRandomized

Problem Description

The given LeetCode problem asks us to design a class called Solution that can take an array of integers and provide two functionalities: resetting the array to its original order and returning a randomly shuffled version of the array. The class should have the following methods implemented:

__init__(self, nums: List[int]): This method initializes the object with the integer array nums. It stores both the original array and a copy that can be modified.
reset(self) -> List[int]: This method resets the modified array back to its original configuration and returns it. Any subsequent calls to shuffle should not be affected by previous shuffles.
shuffle(self) -> List[int]: This function returns a new array that is a random shuffle of the original array. It is important that every permutation of the array is equally likely to ensure fairness.

Intuition

The intuition behind the provided solution is derived from the well-known Fisher-Yates shuffle algorithm, also known as the Knuth shuffle. The Fisher-Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in this case, our integer array. The algorithm produces an unbiased permutation: every permutation is equally likely. The process of the shuffle method works as follows:

We iterate through the array from the beginning to the end.
For each element at index i, we generate a random index j such that i <= j < len(nums).
We then swap the elements at indices i and j.
This swapping ensures all possible permutations of the array are equally likely.

This solution ensures that the shuffling is done in-place, meaning no additional memory is used for the shuffled array except for the input array.

Learn more about Math patterns.

Solution Approach

The algorithm uses the following steps to implement the Solution class and its methods, based on the Fisher-Yates shuffle algorithm:

Class Initialization (__init__):
- The constructor takes an array nums and stores it in self.nums.
- It then creates a copy of this array in self.original to preserve the original order for the reset method later.
Reset Method (reset):
- The reset method is straightforward; it creates a copy of the self.original array to revert self.nums to the original configuration.
- This copy is returned to provide the current state of the array after reset, allowing users to perform shuffling again without any prior shuffle affecting the outcome.
Shuffle Method (shuffle):
- The shuffle method is where the Fisher-Yates algorithm is applied to generate an unbiased random permutation of the array.
- A loop is initiated, starting from the first index (i = 0) up to the length of the array.
- Inside the loop, a random index j is chosen where the condition i <= j < len(nums) holds true. This is done using random.randrange(i, len(self.nums)) to pick a random index in the remaining part of the array.
- The elements at indices i and j are swapped. Python's tuple unpacking feature is a clean way to do this in one line: self.nums[i], self.nums[j] = self.nums[j], self.nums[i].
- This process is repeated for each element until the end of the array is reached, resulting in a randomly shuffled array.

The Fisher-Yates shuffle ensures that every element has an equal chance of being at any position in the final shuffled array, leading to each permutation of the array elements being equally likely. This implementation uses O(n) time where n is the number of elements in the array and O(n) space because it maintains a copy of the original array to support the reset method.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate how the Solution class and its methods work according to the Fisher-Yates shuffle algorithm:

Suppose we have an array nums = [1, 2, 3].

Class Initialization (__init__):
- Upon initialization, self.nums will store [1, 2, 3], and self.original will also store [1, 2, 3].
Reset Method (reset):
- Calling reset() anytime would return [1, 2, 3] since it simply copies the contents of self.original back into self.nums.
Shuffle Method (shuffle):
- Let's say we now call shuffle(). We start with i = 0 and choose a random index j such that 0 <= j < 3 (it could be 0, 1, or 2). Assume j turns out to be 2, so we swap nums[0] with nums[2]. Now the array is [3, 2, 1].
- Next, we increment i to 1 and choose a new j such that 1 <= j < 3. Assume j remains 1 this time, so no swapping is needed, and the array stays [3, 2, 1].
- Finally, for i = 2, we choose j such that 2 <= j < 3, which means j can only be 2. No swapping occurs since i equals j, and the shuffled array remains [3, 2, 1].

In practical implementations, shuffle() would likely produce different results each time, as j would be determined by a random number generator. Imagine calling shuffle() several times; you might see output like [2, 3, 1], [1, 3, 2], or any other permutations of [1, 2, 3].

It's important to note that after shuffling, if we call reset(), we will always get the original nums array [1, 2, 3] back, irrespective of how many times or how the array has been shuffled previously.

Solution Implementation

1from typing import List
2import random
3
4class Solution:
5    def __init__(self, nums: List[int]):
6        # Store the original list of numbers
7        self.nums = nums
8        # Make a copy of the original list to keep it intact for reset purposes
9        self.original = nums.copy()
10
11    def reset(self) -> List[int]:
12        # Reset the nums list to the original configuration
13        self.nums = self.original.copy()
14        # Return the reset list
15        return self.nums
16
17    def shuffle(self) -> List[int]:
18        # Shuffle the list of numbers in-place using the Fisher-Yates algorithm
19        for i in range(len(self.nums)):
20            # Pick a random index from i (inclusive) to the end of the list (exclusive)
21            j = random.randrange(i, len(self.nums))
22            # Swap the current element with the randomly chosen one
23            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
24        # Return the shuffled list
25        return self.nums
26
27# Example of how this class could be used:
28# obj = Solution(nums)
29# param_1 = obj.reset()
30# param_2 = obj.shuffle()
31

1import java.util.Random;
2import java.util.Arrays;
3
4class Solution {
5    private int[] nums;      // Array to store the current state (which can be shuffled)
6    private int[] original;  // Array to store the original state
7    private Random rand;     // Random number generator
8
9    // Constructor that takes an array of integers.
10    // The incoming array represents the initial state.
11    public Solution(int[] nums) {
12        this.nums = nums; // Initialize current state with the incoming array
13        this.original = Arrays.copyOf(nums, nums.length); // Copy the original array
14        this.rand = new Random(); // Instantiate the Random object
15    }
16
17    // This method resets the array to its original configuration and returns it.
18    public int[] reset() {
19        // Restore the original state of array
20        nums = Arrays.copyOf(original, original.length);
21        return nums;
22    }
23
24    // This method returns a random shuffling of the array.
25    public int[] shuffle() {
26        // Loop over the array elements
27        for (int i = 0; i < nums.length; ++i) {
28            // Swap the current element with a randomly selected element from the remaining
29            // portion of the array, starting at the current index to the end of the array.
30            swap(i, i + rand.nextInt(nums.length - i));
31        }
32        // Return the shuffled array
33        return nums;
34    }
35
36    // Helper method to swap two elements in the array.
37    // Takes two indices and swaps the elements at these indices.
38    private void swap(int i, int j) {
39        int temp = nums[i]; // Temporary variable to hold the value of the first element
40        nums[i] = nums[j]; // Assign the value of the second element to the first
41        nums[j] = temp;    // Assign the value of the temporary variable to the second
42    }
43}
44
45/**
46 * The following lines are typically provided in the problem statement on LeetCode.
47 * They indicate how the Solution class can be used once implemented:
48 *
49 * Solution obj = new Solution(nums);
50 * int[] param_1 = obj.reset();
51 * int[] param_2 = obj.shuffle();
52 */
53

1#include <vector>
2#include <algorithm> // For std::copy and std::swap
3#include <cstdlib>   // For std::rand
4
5class Solution {
6public:
7    std::vector<int> nums;      // Vector to store the current state of the array.
8    std::vector<int> original;  // Vector to store the original state of the array.
9
10    // Constructor to initialize the vectors with the input array.
11    Solution(std::vector<int>& nums) {
12        this->nums = nums;
13        this->original.resize(nums.size());
14        std::copy(nums.begin(), nums.end(), original.begin());
15    }
16
17    // Resets the array to its original configuration and returns it.
18    std::vector<int> reset() {
19        std::copy(original.begin(), original.end(), nums.begin());
20        return nums;
21    }
22
23    // Returns a random shuffling of the array.
24    std::vector<int> shuffle() {
25        for (int i = 0; i < nums.size(); ++i) {
26            // Generate a random index j such that i <= j < n
27            int j = i + std::rand() % (nums.size() - i);
28            // Swap nums[i] with nums[j]
29            std::swap(nums[i], nums[j]);
30        }
31        return nums;
32    }
33};
34
35// Example of how to use the class
36/*
37Solution* obj = new Solution(nums); // Create an object of Solution with the initial array nums
38std::vector<int> param_1 = obj->reset(); // Reset the array to its original configuration
39std::vector<int> param_2 = obj->shuffle(); // Get a randomly shuffled array
40delete obj; // Don't forget to delete the object when done to free resources
41*/
42

1// Array to hold the original sequence of numbers.
2let originalNums: number[] = [];
3
4// Function to initialize the array with a set of numbers.
5function initNums(nums: number[]): void {
6    originalNums = nums;
7}
8
9// Function to return the array to its original state.
10function reset(): number[] {
11    // Returning a copy of the original array to prevent outside modifications.
12    return [...originalNums];
13}
14
15// Function to randomly shuffle the elements of the array.
16function shuffle(): number[] {
17    const n = originalNums.length;
18    // Creating a copy of the original array to shuffle.
19    let shuffledNums = [...originalNums];
20    // Implementing Fisher-Yates shuffle algorithm
21    for (let i = 0; i < n; i++) {
22        // Picking a random index within the array.
23        const j = Math.floor(Math.random() * (i + 1));
24        // Swapping elements at indices i and j.
25        [shuffledNums[i], shuffledNums[j]] = [shuffledNums[j], shuffledNums[i]];
26    }
27    return shuffledNums;
28}
29
30// Example of how these functions might be used:
31// Initialize the array
32initNums([1, 2, 3, 4, 5]);
33
34// Reset the array to its original state
35let resetNums = reset();
36console.log(resetNums); // Output: [1, 2, 3, 4, 5]
37
38// Shuffle the array
39let shuffledNums = shuffle();
40console.log(shuffledNums); // Output: [3, 1, 4, 5, 2] (example output, actual output will vary)
41

Time and Space Complexity

`init` method:

Time Complexity: O(n) where n is the length of the nums list, because nums.copy() takes O(n) time.
Space Complexity: O(n), as we are creating a copy of the nums list, which requires additional space proportional to the size of the input list.

`reset` method:

Time Complexity: O(n) due to the self.original.copy() operation, which again takes linear time relative to the size of the nums list.
Space Complexity: O(n) for the new list created by self.original.copy().

`shuffle` method:

Time Complexity: O(n), since it loops through the nums elements once. The operations within the loop each have a constant time complexity (j = random.randrange(i, len(self.nums)) and the swap operation), thus maintaining O(n) overall.
Space Complexity: O(1), because the shuffling is done in place and no additional space proportional to the input size is used.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: