Shuffle an Array - Solution & Explanation
Problem Statement
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 arraynums.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] <= 106- All the elements of
numsare unique. - At most
104calls in total will be made toresetandshuffle.
Approach Overview
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 1: Fisher-Yates Shuffle Algorithm
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'.
Complexity
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
Approach 2: Recursive Permutation Generation
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.
Code
Python
JavaScript
Complexity
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Shuffle an Array | Fisher Yates Algorithm | Leetcode 384 | Live coding session 💯💯💯 • Coding Decoded • 7,841 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shuffle an Array easy or hard?
Shuffle an Array Python/Java solution
How to solve Shuffle an Array in O(n)?
What is the best approach for Shuffle an Array?
Is Shuffle an Array asked at Google/Amazon/Meta?
What data structure is used in Shuffle an Array?
What is the time complexity of Shuffle an Array?
Ready to solve this problem?
Practice Shuffle an Array with our built-in code editor and test cases.
Practice on FleetCode