This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Shuffle a set of numbers without duplicates.

**Example:**

// Init an array with set 1, 2, and 3. int[] nums = {1,2,3}; Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. solution.shuffle(); // Resets the array back to its original configuration [1,2,3]. solution.reset(); // Returns the random shuffling of array [1,2,3]. solution.shuffle();

b'

\n#### Initial Thoughts

\n#### Approach #1 Brute Force [Accepted]

\n

\n#### Approach #2 Fisher-Yates Algorithm [Accepted]

\n

\n

'
\n\n

\nNormally I would display more than two approaches, but shuffling is\ndeceptively easy to do *almost* properly, and the Fisher-Yates algorithm is\nboth the canonical solution and asymptotically optimal.

A few notes on randomness are necessary before beginning - both approaches\ndisplayed below assume that the languages\' pseudorandom number generators\n(PRNGs) are sufficiently random. The sample code uses the simplest techniques\navailable for getting pseudorandom numbers, but for each possible permutation\nof the array to be truly equally likely, more care must be taken. For\nexample, an array of length has distinct permutations. Therefore, in\norder to encode all permutations in an integer space, \nbits are necessary, which may not be guaranteed by the default PRNG.

\n**Intuition**

If we put each number in a "hat" and draw them out at random, the order in\nwhich we draw them will define a random ordering.

\n**Algorithm**

The brute force algorithm essentially puts each number in the aforementioned\n"hat", and draws them at random (without replacement) until there are none\nleft. Mechanically, this is performed by copying the contents of `array`

into\na second auxiliary array named `aux`

before overwriting each element of\n`array`

with a randomly selected one from `aux`

. After selecting each random\nelement, it is removed from `aux`

to prevent duplicate draws. The\nimplementation of `reset`

is simple, as we just store the original state of\n`nums`

on construction.

The correctness of the algorithm follows from the fact that an element\n(without loss of generality) is equally likely to be selected during all\niterations of the `for`

loop. To prove this, observe that the probability of a\nparticular element being chosen on the th iteration (indexed from 0)\nis simply being chosen during the th iteration not being\nchosen before the th iteration. Given that the array to be shuffled has\n elements, this probability is more concretely stated as the following:

\n\n

\nWhen expanded (and rearranged), it looks like this (for sufficiently large\n):

\n\n\n

\nFor the base case (), it is trivial to see that\n. For , the numerator of each fraction\ncan be cancelled with the denominator of the next, leaving the from the\n0th draw as the only uncancelled denominator. Therefore, no matter on which\ndraw an element is drawn, it is drawn with a chance, so each\narray permutation is equally likely to arise.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nThe quadratic time complexity arises from the calls to

\n`list.remove`

(or\n`list.pop`

), which run in linear time. linear list removals occur,\nwhich results in a fairly easy quadratic analysis. \n - \n
Space complexity : \n

\nBecause the problem also asks us to implement

\n`reset`

, we must use linear\nadditional space to store the original array. Otherwise, it would be lost\nupon the first call to`shuffle`

. \n

\n

**Intuition**

We can cut down the time and space complexities of `shuffle`

with a bit of\ncleverness - namely, by swapping elements around within the array itself, we\ncan avoid the linear space cost of the auxiliary array and the linear time\ncost of list modification.

**Algorithm**

The Fisher-Yates algorithm is remarkably similar to the brute force solution.\nOn each iteration of the algorithm, we generate a random integer between the\ncurrent index and the last index of the array. Then, we swap the elements at\nthe current index and the chosen index - this simulates drawing (and\nremoving) the element from the hat, as the next range from which we select a\nrandom index will not include the most recently processed one. One small, yet important\ndetail is that it is possible to swap an element with itself - otherwise, some\narray permutations would be more likely than others. To see this illustrated more\nclearly, consider the animation below:

\n!?!../Documents/384_Shuffle_an_Array.json:697,161!?!

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nThe Fisher-Yates algorithm runs in linear time, as generating a random\nindex and swapping two values can be done in constant time.

\n \n - \n
Space complexity : \n

\nAlthough we managed to avoid using linear space on the auxiliary array\nfrom the brute force approach, we still need it for

\n`reset`

, so we\'re\nstuck with linear space complexity. \n

\n

Analysis written by: @emptyset

\n