Shuffle an Array
MedPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible permutation of the input array beforehand. When a shuffle is requested, one of these pre-computed permutations is chosen at random.
Algorithm
-
- In the constructor, store a copy of the original array.
-
- On the first call to
shuffle(), generate alln!permutations of the array using a recursive backtracking algorithm and store them in a list.
- On the first call to
-
- For subsequent
shuffle()calls, pick a random index from0ton!-1and return the permutation at that index.
- For subsequent
-
- The
reset()method returns the stored original array.
- The
Walkthrough
In this method, we first generate all unique permutations of the original array. This is a one-time operation, typically done during the initialization of the object or on the first call to shuffle(). A standard backtracking algorithm can be used to generate these permutations.
Once we have a list containing all n! permutations, the shuffle() method becomes very simple: it just needs to pick a random index from this list and return the corresponding permutation. The reset() method simply returns the original, unmodified array.
While conceptually straightforward, this approach is highly impractical due to its factorial time and space complexity. It's only feasible for very small arrays.
import java.util.ArrayList;import java.util.List;import java.util.Random; class Solution { private int[] original; private List<int[]> allPermutations; private Random rand; public Solution(int[] nums) { this.original = nums.clone(); this.rand = new Random(); this.allPermutations = new ArrayList<>(); // Pre-computation is too slow to do here, so we do it on the first shuffle call. } // Helper to generate all permutations using backtracking private void generatePermutations(List<Integer> current, boolean[] used, int[] nums) { if (current.size() == nums.length) { allPermutations.add(current.stream().mapToInt(i -> i).toArray()); return; } for (int i = 0; i < nums.length; i++) { if (!used[i]) { used[i] = true; current.add(nums[i]); generatePermutations(current, used, nums); current.remove(current.size() - 1); used[i] = false; } } } public int[] reset() { return original; } public int[] shuffle() { if (allPermutations.isEmpty()) { // One-time expensive setup generatePermutations(new ArrayList<>(), new boolean[original.length], original); } int randomIndex = rand.nextInt(allPermutations.size()); return allPermutations.get(randomIndex); }}Complexity
Time
O(n * n!) for the one-time pre-computation to generate all permutations. Each subsequent call to `shuffle()` is O(1) (or O(n) to copy the array). The `reset()` is O(1) or O(n). The dominant factor is the pre-computation.
Space
O(n * n!) to store all `n!` permutations, each of length `n`. This is prohibitively large for most inputs.
Trade-offs
Pros
Guarantees a uniform distribution if the random index is chosen uniformly.
Once pre-computation is done, subsequent shuffles are very fast.
Cons
Extremely high time complexity for pre-computation.
Extremely high space complexity.
Impractical for arrays with more than a few elements (e.g., n > 10).
This approach shuffles the array by associating each element with a random number and then sorting the elements based on these random numbers. This effectively reorders the array in a random fashion.
Algorithm
-
- Store the original array.
-
- In the
shuffle()method, create a list of pairs.
- In the
-
- Iterate through the original array. For each element, create a pair consisting of the element and a new random number, and add it to the list.
-
- Sort the list of pairs based on the random numbers.
-
- Create a new result array and populate it with the elements from the sorted list of pairs.
-
- Return the result array.
Walkthrough
To shuffle the array, we first create a copy of the original array to avoid modifying it. Then, we create a list of pairs, where each pair consists of an element from the array and a randomly generated number that will act as its sorting key.
After populating this list, we sort it based on the random keys. The sorted list now has the original elements in a new, random order. We then extract these elements in their new order to form the shuffled array.
This method is much more efficient than generating all permutations. However, it has a potential flaw: if two elements are assigned the same random number (a collision), the sorting algorithm's behavior for ties (e.g., stable vs. unstable sort) can introduce bias, meaning not all permutations are equally likely. Using floating-point random numbers reduces the probability of collisions but doesn't eliminate it.
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Random; class Solution { // A simple Pair class for demonstration private static class Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } } private int[] original; private Random rand; public Solution(int[] nums) { this.original = nums.clone(); this.rand = new Random(); } public int[] reset() { return original; } public int[] shuffle() { List<Pair<Integer, Integer>> pairedList = new ArrayList<>(); for (int num : original) { pairedList.add(new Pair<>(num, rand.nextInt())); } // Sort the list based on the random keys Collections.sort(pairedList, (a, b) -> a.getValue().compareTo(b.getValue())); int[] shuffled = new int[original.length]; for (int i = 0; i < original.length; i++) { shuffled[i] = pairedList.get(i).getKey(); } return shuffled; }}Complexity
Time
O(n log n) for each `shuffle()` call, dominated by the sorting step.
Space
O(n) to store the list of pairs and the resulting shuffled array.
Trade-offs
Pros
Much more efficient than generating all permutations.
Relatively easy to implement.
Cons
Slower than the optimal Fisher-Yates shuffle.
May not produce a perfectly uniform distribution of permutations due to potential random number collisions and the behavior of the sorting algorithm on ties.
This is the canonical and most efficient algorithm for generating a random permutation of a finite sequence. It works by iterating through the array and, for each element, swapping it with another element chosen randomly from the part of the array that has not yet been shuffled.
Algorithm
-
- Store the original array configuration.
-
- For the
shuffle()method, create a copy of the original array.
- For the
-
- Iterate from the last index
n-1down to1.
- Iterate from the last index
-
- In each iteration
i, generate a random indexjin the range[0, i].
- In each iteration
-
- Swap the elements at indices
iandjin the copied array.
- Swap the elements at indices
-
- After the loop, return the shuffled copy.
-
- The
reset()method simply returns the original array.
- The
Walkthrough
The Fisher-Yates algorithm (also known as the Knuth shuffle) provides an unbiased permutation in linear time. The core idea is to shuffle the array in place.
We iterate through the array from the last element down to the second element. In each iteration i, we generate a random index j from 0 to i (inclusive). We then swap the element at the current index i with the element at the random index j. By doing this, the element that was originally at index i is now randomly placed somewhere in the prefix 0...i, and an element from that prefix is moved to position i.
After the first step (for i = n-1), any of the n elements has a 1/n chance of being in the last position. After the second step (for i = n-2), any of the remaining n-1 elements has a 1/(n-1) chance of being in the second-to-last position, and so on. This process guarantees that every permutation is equally likely.
For our implementation, we store the original array. The shuffle method first creates a copy of the original array and then applies the Fisher-Yates algorithm to this copy before returning it. This ensures the original array remains unchanged for future reset calls.
import java.util.Random; class Solution { private int[] original; private Random rand; public Solution(int[] nums) { this.original = nums.clone(); this.rand = new Random(); } /** Resets the array to its original configuration and return it. */ public int[] reset() { return original; } /** Returns a random shuffling of the array. */ public int[] shuffle() { int[] shuffled = original.clone(); // Always start with a fresh copy // Fisher-Yates shuffle algorithm for (int i = shuffled.length - 1; i > 0; i--) { // Pick a random index from 0 to i (inclusive) int j = rand.nextInt(i + 1); // Swap shuffled[i] with the element at random index j int temp = shuffled[i]; shuffled[i] = shuffled[j]; shuffled[j] = temp; } return shuffled; }}Complexity
Time
O(n) for each `shuffle()` call. The loop runs `n-1` times, and each operation inside (random number generation, swap) is O(1). `reset()` is O(n) to return a copy or O(1) to return a reference.
Space
O(n) to store the original array. The `shuffle()` method also uses O(n) auxiliary space to create a copy to shuffle, so the original array is preserved.
Trade-offs
Pros
Optimal time complexity of O(n).
Guarantees a perfectly uniform random permutation.
Efficient in terms of space.
It is the standard, industry-accepted algorithm for this problem.
Cons
Slightly more complex to understand the proof of correctness compared to the sorting approach, but the implementation is simple.
Solutions
Solution
class Solution {private int[] nums;private int[] original;private Random rand;public Solution(int[] nums) { this.nums = nums; this.original = Arrays.copyOf(nums, nums.length); this.rand = new Random(); }public int[] reset() { nums = Arrays.copyOf(original, original.length); return nums; }public int[] shuffle() { for (int i = 0; i < nums.length; ++i) { swap(i, i + rand.nextInt(nums.length - i)); } return nums; }private void swap(int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }} /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int[] param_1 = obj.reset(); * int[] param_2 = obj.shuffle(); *//** * @param {number[]} nums */ const Solution = function (nums) { this.nums = nums || [];};/** * Resets the array to its original configuration and return it. * @return {number[]} */ Solution.prototype.reset = function () { return this.nums; };/** * Returns a random shuffling of the array. * @return {number[]} */ Solution.prototype.shuffle = function () { let a = this.nums.slice(); for (let i = 0; i < a.length; i++) { let rand = Math.floor(Math.random() * (a.length - i)) + i; let tmp = a[i]; a[i] = a[rand]; a[rand] = tmp; } return a; }; /** * Your Solution object will be instantiated and called as such: * var obj = Object.create(Solution).createNew(nums) * var param_1 = obj.reset() * var param_2 = obj.shuffle() */ // lexicographical-numbers/** * @param {number} n * @return {number[]} */ var lexicalOrder = function ( n,) { let ans = []; function dfs(u) { if (u > n) { return; } ans.push(u); for (let i = 0; i < 10; ++i) { dfs(u * 10 + i); } } for (let i = 1; i < 10; ++i) { dfs(i); } return ans;};class Solution {public: vector<int> nums; vector<int> original; Solution(vector<int> &nums) { this->nums = nums; this->original.resize(nums.size()); copy(nums.begin(), nums.end(), original.begin()); } vector<int> reset() { copy(original.begin(), original.end(), nums.begin()); return nums; } vector<int> shuffle() { for (int i = 0; i < nums.size(); ++i) { int j = i + rand() % (nums.size() - i); swap(nums[i], nums[j]); } return nums; }}; /** * 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(); */class Solution: # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.reset() # param_2 = obj.shuffle() def __init__(self, nums: List[int]): self . nums = nums self . original = nums . copy() def reset(self) -> List[int]: self . nums = self . original . copy() return self . nums def shuffle(self) -> List[int]: for i in range(len(self . nums)): j = random . randrange(i, len(self . nums)) self . nums[i], self . nums[j] = self . nums[j], self . nums[i] return self . numsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.