Shuffle an Array Problem

Problem

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

  • Solution(int[] nums) Initializes the object with the integer array nums.
  • int[] reset() Resets the array to its original configuration and returns it.
  • int[] shuffle() Returns a random shuffling of the array.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

**Input**
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
**Output**
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

**Explanation**
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Examples

Solution

Method 1 - Using Fisher Yates Shuffle

We have seen Fisher-Yates Shuffle. Now, we can use it here.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    private final int[] original;
    private int[] shuffle;
    final Random rand;
    public Solution(int[] nums) {
        this.original = nums;
        shuffle = Arrays.copyOf(nums, nums.length);
        rand = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        shuffle = Arrays.copyOf(original, original.length);
        return shuffle;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for (int i = 0; i < shuffle.length; i++) {
            int idx = i + rand.nextInt(shuffle.length - i);
            //swap
            int tmp = shuffle[idx];
            shuffle[idx] = shuffle[i];
            shuffle[i] = tmp;
        }

        return shuffle;
    }
}

Method 2 – Reservoir Sampling

Intuition

Reservoir sampling is a technique for randomly selecting k items from a stream of unknown size, ensuring each item has equal probability. For shuffling, we can use a similar idea: for each position, pick a random element from the remaining pool and swap. This is essentially the Fisher-Yates shuffle, but the term ‘reservoir sampling’ is sometimes used for the streaming version.

Approach

  1. Initialization:
    • Store the original array for reset operations.
  2. Reset:
    • Return the array to its original configuration.
  3. Shuffle (Reservoir Sampling):
    • For each index, pick a random index from the current position to the end and swap the elements.
    • This is equivalent to Fisher-Yates, but can be adapted for streaming data.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <random>
using namespace std;
class Solution {
    vector<int> orig, arr;
    mt19937 gen;
public:
    Solution(vector<int>& nums) : orig(nums), arr(nums), gen(random_device{}()) {}
    vector<int> reset() {
        arr = orig;
        return arr;
    }
    vector<int> shuffle() {
        int n = arr.size();
        for (int i = 0; i < n; ++i) {
            uniform_int_distribution<> d(i, n - 1);
            int j = d(gen);
            swap(arr[i], arr[j]);
        }
        return arr;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import "math/rand"
type Solution struct {
    orig, arr []int
}
func Constructor(nums []int) Solution {
    o := make([]int, len(nums))
    copy(o, nums)
    return Solution{o, o}
}
func (s *Solution) Reset() []int {
    copy(s.arr, s.orig)
    return s.arr
}
func (s *Solution) Shuffle() []int {
    n := len(s.arr)
    for i := 0; i < n; i++ {
        j := i + rand.Intn(n-i)
        s.arr[i], s.arr[j] = s.arr[j], s.arr[i]
    }
    return s.arr
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    private final int[] orig;
    private int[] arr;
    private final Random rand;
    public Solution(int[] nums) {
        orig = nums.clone();
        arr = nums.clone();
        rand = new Random();
    }
    public int[] reset() {
        arr = orig.clone();
        return arr;
    }
    public int[] shuffle() {
        for (int i = 0; i < arr.length; i++) {
            int j = i + rand.nextInt(arr.length - i);
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
        return arr;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import kotlin.random.Random
class Solution(nums: IntArray) {
    private val orig = nums.copyOf()
    private var arr = nums.copyOf()
    fun reset(): IntArray {
        arr = orig.copyOf()
        return arr
    }
    fun shuffle(): IntArray {
        for (i in arr.indices) {
            val j = (i until arr.size).random()
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
        return arr
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import random
class Solution:
    def __init__(self, nums: list[int]):
        self.orig = nums[:]
        self.arr = nums[:]
    def reset(self) -> list[int]:
        self.arr = self.orig[:]
        return self.arr
    def shuffle(self) -> list[int]:
        n = len(self.arr)
        for i in range(n):
            j = random.randint(i, n - 1)
            self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
        return self.arr
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

use rand::{thread_rng, Rng};
struct Solution {
    orig: Vec<i32>,
    arr: Vec<i32>,
}
impl Solution {
    fn new(nums: Vec<i32>) -> Self {
        Self { orig: nums.clone(), arr: nums }
    }
    fn reset(&mut self) -> Vec<i32> {
        self.arr = self.orig.clone();
        self.arr.clone()
    }
    fn shuffle(&mut self) -> Vec<i32> {
        let n = self.arr.len();
        let mut rng = thread_rng();
        for i in 0..n {
            let j = rng.gen_range(i..n);
            self.arr.swap(i, j);
        }
        self.arr.clone()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    private orig: number[];
    private arr: number[];
    constructor(nums: number[]) {
        this.orig = nums.slice();
        this.arr = nums.slice();
    }
    reset(): number[] {
        this.arr = this.orig.slice();
        return this.arr;
    }
    shuffle(): number[] {
        for (let i = 0; i < this.arr.length; i++) {
            const j = i + Math.floor(Math.random() * (this.arr.length - i));
            [this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
        }
        return this.arr;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array. Each shuffle and reset operation is linear.
  • 🧺 Space complexity: O(n), for storing the original and working arrays.