Shuffle an Array

Medium Design Data Structures Randomized Algorithms Original on LeetCode

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 nums are distinct.
  • At most 10^4 calls in total to reset and shuffle.

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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (draw from a pool)O(n²) per shuffleO(n)
Optimal (Fisher-Yates)O(n) per callO(n)

1Brute force (draw from a pool)

TimeO(n²) per shufflen draws, each removing from an array list in O(n).
SpaceO(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.

  1. Constructor: save a copy of nums.
  2. reset(): return a copy of the saved array.
  3. 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;
    }
}

2Optimal (Fisher-Yates)

TimeO(n) per callOne swap per position.
SpaceO(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.

  1. Constructor: save a copy of nums.
  2. reset(): return a copy of the saved array.
  3. 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;
    }
}

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.