grid47 Exploring patterns and algorithms
Sep 29, 2024
5 min read
Solution to LeetCode 384: Shuffle an Array Problem
You are given an integer array nums. Design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array nums.
Example: nums = [1, 2, 3]
Constraints:
• 1 <= nums.length <= 50
• -10^6 <= nums[i] <= 10^6
• All elements of nums are unique.
Output: The output consists of the array after applying the shuffle or reset method.
Example: Output: [3, 1, 2] after shuffle, [1, 2, 3] after reset
Constraints:
• The result of shuffle should be a random permutation of the array.
• The result of reset should return the array in its original configuration.
Goal: The goal is to implement a random shuffle that gives each permutation an equal probability.
Steps:
• Save the original configuration of the array.
• Use the Fisher-Yates (or Knuth) algorithm to shuffle the array randomly.
• On calling reset, return the original configuration.
• On calling shuffle, return a new randomly shuffled version of the array.
Goal: Ensure that the solution is efficient and works within the problem's constraints.
Steps:
• The solution should handle up to 10^4 shuffle and reset operations efficiently.
Assumptions:
• The input array is non-empty and has unique elements.
• Input: Input: [1, 2, 3]
• Explanation: The shuffle operation should return a random permutation of [1, 2, 3] such as [3, 1, 2]. The reset operation should return the array to its original form [1, 2, 3].
Approach: The approach involves using a simple but efficient algorithm for shuffling (like Fisher-Yates) and maintaining the original array for reset.
Observations:
• Randomly shuffling requires a well-known algorithm to ensure each permutation has equal probability.
• By maintaining the original array and shuffling a copy, we can ensure efficient reset and shuffle operations.
Steps:
• Store the initial array in a member variable.
• Implement the shuffle method using the Fisher-Yates algorithm to randomly swap elements in the array.
• Implement the reset method to return the original array.
Empty Inputs:
• The problem guarantees that nums will have at least one element.
Large Inputs:
• The solution should handle cases where nums has up to 50 elements efficiently.
Special Values:
• Ensure that shuffle works even when nums has only one element, as this is a valid edge case.
Constraints:
• Ensure the shuffle operation is random but efficient.
classSolution {
vector<int> arr;
public:Solution(vector<int>& nums) {
arr = nums;
}
vector<int> reset() {
return arr;
}
vector<int> shuffle() {
vector<int> stk(arr);
int n = stk.size();
for(int i =0; i < n; i++) {
int j = rand() % (n - i);
swap(stk[i + j], stk[i]);
}
return stk;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
1 : Class Definition
classSolution {
This line defines the class `Solution` that will contain methods to reset and shuffle an array.
2 : Member Variable
vector<int> arr;
A private member variable `arr` is defined to store the original array passed to the constructor.
3 : Access Specifier
public:
The `public` access specifier follows, meaning that the subsequent methods will be accessible outside the class.
4 : Constructor
Solution(vector<int>& nums) {
The constructor `Solution` takes a reference to a vector `nums` and initializes the member variable `arr` with the input array.
5 : Constructor Logic
arr = nums;
The constructor assigns the input array `nums` to the member variable `arr` to store the original array.
6 : Reset Method
vector<int> reset() {
The `reset` method returns the original array stored in `arr`.
7 : Reset Logic
return arr;
The `reset` method simply returns the original array `arr`.
8 : Shuffle Method
vector<int> shuffle() {
The `shuffle` method returns a randomly shuffled version of the original array `arr`.
9 : Shuffling Logic
vector<int> stk(arr);
A new vector `stk` is created and initialized with the elements of the original array `arr`.
10 : Size Calculation
int n = stk.size();
The size of the vector `stk` is stored in the variable `n`.
11 : Shuffling Loop
for(int i =0; i < n; i++) {
This loop iterates over each element in the vector `stk` to perform the shuffling.
12 : Random Index Generation
int j = rand() % (n - i);
A random index `j` is generated within the remaining unshuffled part of the array.
13 : Swapping Elements
swap(stk[i + j], stk[i]);
The elements at indices `i` and `i + j` are swapped to shuffle the array.
14 : Return Shuffled Array
return stk;
The shuffled array `stk` is returned from the `shuffle` method.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Both the shuffle and reset operations run in linear time.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is linear, as we store a copy of the original array and work with a temporary shuffled array.
