Shuffle an Array
Medium · Math · Array · Math · Design · Randomized
Problem
Design a class that shuffles an array of distinct integers so that every order is equally likely, and can also give back the original order.
Implement Solution:
- Solution(nums) stores the array.
- reset() returns the array in its original order.
- shuffle() returns a random rearrangement of the array. Each of the n! orders must have the same probability, 1 / n!.
The results are random, so a test checks that every result is a rearrangement of nums, that reset() returns the original, and, over long runs of shuffle(), that every value lands at every position (and, for up to four values, every order comes up) about equally often.
Examples
Input: ops = ["Solution","shuffle","reset","shuffle"], vals = [[[4,8,15]],[],[],[]] Output: for example [null,[15,4,8],[4,8,15],[8,4,15]]
Each shuffle is one of the 6 orders, each with probability 1/6; reset returns [4,8,15]. Any other pair of orders is just as correct.
Input: ops = ["Solution","reset","shuffle"], vals = [[[-2,0]],[],[]] Output: for example [null,[-2,0],[0,-2]]
With two values, shuffle returns either order with probability 1/2.
Constraints
- 1 <= len(nums) <= 50
- -10^6 <= nums[i] <= 10^6
- All values in nums are distinct
- At most 10^4 calls to reset and shuffle in total
Approaches
- Draw a random remaining value and remove it — time O(n²) per shuffle, space O(n)
Follow-up
How would you shuffle a stream too long to hold in memory, or pick k items uniformly from it? Reservoir sampling keeps k items and replaces one with probability k / i when the i-th item arrives; it is Fisher–Yates run as the data arrives.
Related problems
Start free on Cariara · Coding problems · System design studio
