Shuffle an Array
Shuffle an Array is a medium design data structures problem solved with the randomized algorithms pattern.
The best approach, optimal (fisher-yates), runs in O(n) per call time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (draw from a pool) up.
Problem
Design a class that shuffles an array of distinct integers uniformly at random: every one of the n! orders must be equally likely to come out of a shuffle.
Solution(int[] nums)stores the array.int[] reset()returns the array in its original order.int[] shuffle()returns a random order of the array’s elements.
Examples
Example 1
- Input
Solution([4, 7, 9]), shuffle(), reset(), shuffle()- Output
[9, 4, 7], [4, 7, 9], [7, 9, 4]- Why
- Each shuffle may return any of the 6 orders, all equally likely; reset always returns the original order.
Example 2
- Input
Solution([5]), shuffle(), reset()- Output
[5], [5]- Why
- A single element has only one order.
Constraints
1 <= nums.length <= 50-10^6 <= nums[i] <= 10^6- All elements of
numsare distinct. - At most
10^4calls in total toresetandshuffle.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (draw from a pool) | O(n²) per shuffle | O(n) |
| Optimal (Fisher-Yates) | O(n) per call | O(n) |
1Brute force (draw from a pool)
O(n²) per shufflen draws, each removing from an array list in O(n).O(n)The saved original plus the pool and result.Put all elements in a pool. To shuffle, repeatedly pick a uniformly random element from the pool, append it to the result and remove it from the pool. Every order comes out with probability 1 / n!, but removing from the middle of a list costs O(n) each time.
- Constructor: save a copy of nums.
- reset(): return a copy of the saved array.
- shuffle(): copy the saved elements into a list pool; for each output slot pick a random index j in the pool, take pool[j] and remove it.
class Solution {
private final int[] original;
private final Random rng = new Random();
public Solution(int[] nums) {
original = nums.clone();
}
public int[] reset() {
return original.clone();
}
public int[] shuffle() {
List<Integer> pool = new ArrayList<>();
for (int x : original) pool.add(x);
int[] out = new int[original.length];
for (int i = 0; i < out.length; i++) {
int j = rng.nextInt(pool.size());
out[i] = pool.remove(j);
}
return out;
}
}import random
class Solution:
def __init__(self, nums: List[int]):
self.original = list(nums)
def reset(self) -> List[int]:
return list(self.original)
def shuffle(self) -> List[int]:
pool = list(self.original)
out = []
while pool:
j = random.randrange(len(pool))
out.append(pool.pop(j))
return outclass Solution {
public:
Solution(vector<int>& nums) : original(nums), rng(random_device{}()) {}
vector<int> reset() {
return original;
}
vector<int> shuffle() {
vector<int> pool = original;
vector<int> out;
while (!pool.empty()) {
uniform_int_distribution<int> pick(0, (int)pool.size() - 1);
int j = pick(rng);
out.push_back(pool[j]);
pool.erase(pool.begin() + j);
}
return out;
}
private:
vector<int> original;
mt19937 rng;
};class Solution {
constructor(nums) {
this.original = [...nums];
}
reset() {
return [...this.original];
}
shuffle() {
const pool = [...this.original];
const out = [];
while (pool.length > 0) {
const j = Math.floor(Math.random() * pool.length);
out.push(pool.splice(j, 1)[0]);
}
return out;
}
}2Optimal (Fisher-Yates)
O(n) per callOne swap per position.O(n)The saved original and the array being returned.Shuffle a working copy in place. Walk i from the last index down to 1 and swap a[i] with a[j], where j is uniform in [0, i]. Position i receives each still-unplaced element with equal chance, exactly like the pool method, but a swap costs O(1) instead of a removal.
- Constructor: save a copy of nums.
- reset(): return a copy of the saved array.
- shuffle(): a = copy of the saved array; for i = n - 1 down to 1, pick j in [0, i] and swap a[i], a[j]; return a.
class Solution {
private final int[] original;
private final Random rng = new Random();
public Solution(int[] nums) {
original = nums.clone();
}
public int[] reset() {
return original.clone();
}
public int[] shuffle() {
int[] a = original.clone();
for (int i = a.length - 1; i > 0; i--) {
int j = rng.nextInt(i + 1);
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
return a;
}
}import random
class Solution:
def __init__(self, nums: List[int]):
self.original = list(nums)
def reset(self) -> List[int]:
return list(self.original)
def shuffle(self) -> List[int]:
a = list(self.original)
for i in range(len(a) - 1, 0, -1):
j = random.randint(0, i)
a[i], a[j] = a[j], a[i]
return aclass Solution {
public:
Solution(vector<int>& nums) : original(nums), rng(random_device{}()) {}
vector<int> reset() {
return original;
}
vector<int> shuffle() {
vector<int> a = original;
for (int i = (int)a.size() - 1; i > 0; i--) {
uniform_int_distribution<int> pick(0, i);
swap(a[i], a[pick(rng)]);
}
return a;
}
private:
vector<int> original;
mt19937 rng;
};class Solution {
constructor(nums) {
this.original = [...nums];
}
reset() {
return [...this.original];
}
shuffle() {
const a = [...this.original];
for (let i = a.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
}Edge cases to test
- A single element: shuffle can only return it unchanged
- reset after several shuffles must give back the original order, not the last shuffle
- Swapping each position with any position in the whole array (not just the unshuffled part) gives a biased result
Hints
Hint 1
Keep an untouched copy of the input so reset is trivial.
Hint 2
Build the shuffled array position by position: each slot takes an element chosen uniformly from those not used yet.
Hint 3
Do that in place: for i from n - 1 down to 1, swap a[i] with a[j] for a random j in [0, i]. This is the Fisher-Yates shuffle.
FAQ
What is the best time complexity for Shuffle an Array?
Optimal (Fisher-Yates) runs in O(n) per call time and O(n) extra space. One swap per position.
Which pattern does Shuffle an Array use?
It is a design data structures problem that uses the randomized algorithms pattern.
Is there a brute force solution for Shuffle an Array?
Yes. Brute force (draw from a pool) takes O(n²) per shuffle time and O(n) space. Put all elements in a pool.
Which edge cases should I test for Shuffle an Array?
A single element: shuffle can only return it unchanged; reset after several shuffles must give back the original order, not the last shuffle; Swapping each position with any position in the whole array (not just the unshuffled part) gives a biased result.