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.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the integer array nums.int[] reset() Resets the array to its original configuration and returns it.int[] shuffle() Returns a random shuffling of the array.
Example 1:
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
Constraints:
1 <= nums.length <= 50-106 <= nums[i] <= 106nums are unique.104 calls in total will be made to reset and shuffle.Problem Overview: Design a data structure that stores an integer array, supports resetting it to the original configuration, and returns a uniformly random permutation each time shuffle() is called.
Approach 1: Recursive Permutation Generation (O(n! * n) time, O(n) space)
This approach generates permutations of the array recursively and randomly selects one. At each recursion level, pick an element, append it to the current permutation, and recursively permute the remaining elements. Because there are n! possible permutations and building each permutation costs up to O(n), the total time becomes O(n! * n). While conceptually simple, it is extremely inefficient for larger arrays and not suitable for production or interview settings. The idea mainly demonstrates how permutations work using recursion on an array.
Approach 2: Fisher-Yates Shuffle Algorithm (O(n) time, O(1) space)
The Fisher-Yates algorithm produces a perfectly uniform random permutation in linear time. Iterate through the array from index 0 to n - 1. For each position i, generate a random index j between i and n - 1, then swap nums[i] and nums[j]. This ensures every element has an equal probability of appearing in each position. The algorithm runs in O(n) time and uses O(1) additional space since swaps occur in place. Random index generation uses concepts from math and randomized algorithms.
The class design stores two arrays: the original configuration and a working copy used for shuffling. The reset() operation simply returns the original array or restores the working copy from it. Each call to shuffle() performs the Fisher-Yates process on the working array to produce a new random ordering.
Recommended for interviews: Interviewers expect the Fisher-Yates shuffle. It demonstrates understanding of uniform random permutations and in-place algorithms. Mentioning permutation generation shows baseline understanding, but the linear-time Fisher-Yates approach signals strong knowledge of randomized algorithm design.
The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient algorithm for generating a random permutation of a finite sequence. The algorithm works by iterating backward through the array and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet.
In the C implementation, we first allocate memory for the 'Solution' structure. We perform a deep copy of the input array for both the 'original' and 'array' members of the structure. The 'reset' function restores the 'array' to its original configuration, while the 'shuffle' function uses the Fisher-Yates algorithm to shuffle the 'array'. We clean up memory in 'solutionFree'.
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
This approach involves generating a permutation recursively by picking an element and placing it at different positions. This is less efficient than the Fisher-Yates method and not suitable for large arrays.
In this Python solution, we recursively generate a permutation by swapping the current element with any element after it. This ensures that all permutations are equally probable, though it's less efficient for large arrays compared to Fisher-Yates.
Python
JavaScript
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Fisher-Yates Shuffle Algorithm | Time Complexity: O(n) for both reset and shuffle functions. |
| Recursive Permutation Generation | Time Complexity: O(n!) because it attempts every permutation recursively. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Permutation Generation | O(n! * n) | O(n) | Conceptual understanding of permutations or recursion |
| Fisher-Yates Shuffle | O(n) | O(1) | Standard approach for uniformly shuffling arrays in interviews and production |
Shuffle an Array | Fisher Yates Algorithm | Leetcode 384 | Live coding session 💯💯💯 • Coding Decoded • 7,751 views views
Watch 9 more video solutions →Practice Shuffle an Array with our built-in code editor and test cases.
Practice on FleetCode