Watch 10 video solutions for Shuffle an Array, a medium level problem involving Array, Math, Design. This walkthrough by NeetCodeIO has 19,611 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |