384. Shuffle an Array
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 arraynums
. 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 indexj
such thati <= j < len(nums)
. - We then swap the elements at indices
i
andj
. - 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 inself.nums
. - It then creates a copy of this array in
self.original
to preserve the original order for thereset
method later.
- The constructor takes an array
-
Reset Method (
reset
):- The
reset
method is straightforward; it creates a copy of theself.original
array to revertself.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.
- The
-
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 conditioni <= j < len(nums)
holds true. This is done usingrandom.randrange(i, len(self.nums))
to pick a random index in the remaining part of the array. - The elements at indices
i
andj
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
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 EvaluatorExample 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]
, andself.original
will also store[1, 2, 3]
.
- Upon initialization,
-
Reset Method (
reset
):- Calling
reset()
anytime would return[1, 2, 3]
since it simply copies the contents ofself.original
back intoself.nums
.
- Calling
-
Shuffle Method (
shuffle
):- Let's say we now call
shuffle()
. We start withi = 0
and choose a random indexj
such that0 <= j < 3
(it could be 0, 1, or 2). Assumej
turns out to be 2, so we swapnums[0]
withnums[2]
. Now the array is[3, 2, 1]
. - Next, we increment
i
to 1 and choose a newj
such that1 <= j < 3
. Assumej
remains 1 this time, so no swapping is needed, and the array stays[3, 2, 1]
. - Finally, for
i = 2
, we choosej
such that2 <= j < 3
, which meansj
can only be 2. No swapping occurs sincei
equalsj
, and the shuffled array remains[3, 2, 1]
.
- Let's say we now call
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, becausenums.copy()
takesO(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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!