Shuffle an Array

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:

**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](fisher-yates-shuffle). Now, we can use it here.

Code:

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

C++

#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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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()
    }
}

TypeScript

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.