Skip to content
Onsite
71 / 72

Shuffle an Array

MediumP2Coding

Implement the Fisher-Yates shuffle with the random choices supplied as input, so that the result is deterministic.

Work on a copy a of nums. For i from n - 1 down to 1, take the next roll j = rolls[n - 1 - i] (so rolls are consumed in order) and swap a[i] with a[j]. Each roll satisfies 0 <= j <= i. Return a. The input array must not be changed.

In a real shuffle each roll would be a uniform random integer in [0, i]; that is what makes all n! orderings equally likely.

Example 1

Input
nums = [1,2,3], rolls = [1,0]
Output
[3,1,2]
Why
i=2, j=1: [1,3,2]; then i=1, j=0: [3,1,2].

Example 2

Input
nums = [1,2,3], rolls = [2,1]
Output
[1,2,3]
Why
i=2, j=2 swaps with itself; i=1, j=1 does too, so nothing changes.

Example 3

Input
nums = [5], rolls = []
Output
[5]

Constraints

  • 1 <= nums.length <= 10^4
  • rolls.length == nums.length - 1
  • For the roll used at step i, 0 <= rolls[n - 1 - i] <= i
  • -10^6 <= nums[i] <= 10^6

Hints

Run checks the 3 visible tests, Submit all 10.