🎨Now live: Try our Free AI Image Generation Feature

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:
- reset() - Resets the array to its original configuration and returns it.
- 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
- Initialization: In the constructor, store both the original array and the working array (which will be shuffled).
- Reset: Simply return the original array, or copy it to avoid altering it.
- 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;
};