Shuffle an Array — Fisher-Yates O(n) Uniform Shuffle [Google Easy]

Problem Statement

Implement Solution(nums), reset() and shuffle(). Shuffle must be uniformly random.

Intuition — Fisher-Yates
C++ Solution
Java Solution
Python Solution
Complexity: O(n) per shuffle, O(n) space

Intuition — Fisher-Yates

For i from n-1 downto 1: swap nums[i] with nums[random(0, i)]. Every permutation has probability 1/n!.

Why is it uniform? Element at position i has probability 1/n of landing in position n-1, then 1/(n-1) of landing in n-2, etc.

C++ Solution

#include <vector>
#include <algorithm>
#include <random>
using namespace std;
class Solution {
    vector<int> original, nums;
public:
    Solution(vector<int>& nums) : original(nums), nums(nums) {}
    vector<int> reset() { nums = original; return nums; }
    vector<int> shuffle() {
        for (int i = (int)nums.size()-1; i > 0; i--) {
            int j = rand() % (i+1);
            swap(nums[i], nums[j]);
        }
        return nums;
    }
};

Java Solution

import java.util.Random;
class Solution {
    int[] original, nums;
    Random rand = new Random();
    public Solution(int[] nums) {
        this.original = nums.clone();
        this.nums = nums.clone();
    }
    public int[] reset() { nums = original.clone(); return nums; }
    public int[] shuffle() {
        for (int i = nums.length-1; i > 0; i--) {
            int j = rand.nextInt(i+1);
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
        return nums;
    }
}

Python Solution

import random
class Solution:
    def __init__(self, nums):
        self.original = nums[:]
        self.nums = nums[:]
    def reset(self):
        self.nums = self.original[:]
        return self.nums
    def shuffle(self):
        for i in range(len(self.nums)-1, 0, -1):
            j = random.randint(0, i)
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums

Problem Statement

Intuition — Fisher-Yates

C++ Solution

Java Solution

Python Solution

Complexity: O(n) per shuffle, O(n) space