Scale Engineer

Shuffle an Array

Med
#0371Time: O(n * n!) for the one-time pre-computation to generate all permutations. Each subsequent call to `shuffle()` is O(1) (or O(n) to copy the array). The `reset()` is O(1) or O(n). The dominant factor is the pre-computation.Space: O(n * n!) to store all `n!` permutations, each of length `n`. This is prohibitively large for most inputs.3 companies
Patterns
MathDesignRandomized
Data structures
Array
Companies
J.P. MorganLinkedInNvidia

Prompt

[Fetch error]

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible permutation of the input array beforehand. When a shuffle is requested, one of these pre-computed permutations is chosen at random.

Algorithm

    1. In the constructor, store a copy of the original array.
    1. On the first call to shuffle(), generate all n! permutations of the array using a recursive backtracking algorithm and store them in a list.
    1. For subsequent shuffle() calls, pick a random index from 0 to n!-1 and return the permutation at that index.
    1. The reset() method returns the stored original array.

Walkthrough

In this method, we first generate all unique permutations of the original array. This is a one-time operation, typically done during the initialization of the object or on the first call to shuffle(). A standard backtracking algorithm can be used to generate these permutations.

Once we have a list containing all n! permutations, the shuffle() method becomes very simple: it just needs to pick a random index from this list and return the corresponding permutation. The reset() method simply returns the original, unmodified array.

While conceptually straightforward, this approach is highly impractical due to its factorial time and space complexity. It's only feasible for very small arrays.

import java.util.ArrayList;import java.util.List;import java.util.Random; class Solution {    private int[] original;    private List<int[]> allPermutations;    private Random rand;     public Solution(int[] nums) {        this.original = nums.clone();        this.rand = new Random();        this.allPermutations = new ArrayList<>();        // Pre-computation is too slow to do here, so we do it on the first shuffle call.    }     // Helper to generate all permutations using backtracking    private void generatePermutations(List<Integer> current, boolean[] used, int[] nums) {        if (current.size() == nums.length) {            allPermutations.add(current.stream().mapToInt(i -> i).toArray());            return;        }        for (int i = 0; i < nums.length; i++) {            if (!used[i]) {                used[i] = true;                current.add(nums[i]);                generatePermutations(current, used, nums);                current.remove(current.size() - 1);                used[i] = false;            }        }    }     public int[] reset() {        return original;    }     public int[] shuffle() {        if (allPermutations.isEmpty()) {            // One-time expensive setup            generatePermutations(new ArrayList<>(), new boolean[original.length], original);        }        int randomIndex = rand.nextInt(allPermutations.size());        return allPermutations.get(randomIndex);    }}

Complexity

Time

O(n * n!) for the one-time pre-computation to generate all permutations. Each subsequent call to `shuffle()` is O(1) (or O(n) to copy the array). The `reset()` is O(1) or O(n). The dominant factor is the pre-computation.

Space

O(n * n!) to store all `n!` permutations, each of length `n`. This is prohibitively large for most inputs.

Trade-offs

Pros

  • Guarantees a uniform distribution if the random index is chosen uniformly.

  • Once pre-computation is done, subsequent shuffles are very fast.

Cons

  • Extremely high time complexity for pre-computation.

  • Extremely high space complexity.

  • Impractical for arrays with more than a few elements (e.g., n > 10).

Solutions

class Solution {private  int[] nums;private  int[] original;private  Random rand;public  Solution(int[] nums) {    this.nums = nums;    this.original = Arrays.copyOf(nums, nums.length);    this.rand = new Random();  }public  int[] reset() {    nums = Arrays.copyOf(original, original.length);    return nums;  }public  int[] shuffle() {    for (int i = 0; i < nums.length; ++i) {      swap(i, i + rand.nextInt(nums.length - i));    }    return nums;  }private  void swap(int i, int j) {    int t = nums[i];    nums[i] = nums[j];    nums[j] = t;  }} /** * Your Solution object will be instantiated and called as such: * Solution     obj = new Solution(nums); * int[] param_1 = obj.reset(); * int[] param_2 =     obj.shuffle(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem