Shuffle an Array solution and explanation
Google
9 more videos on this problem
Shuffle an Array | Fisher Yates Algorithm | Leetcode 384 | Live coding session 💯💯💯Coding Decoded · 12:18 · 7K views
Google Coding Interview Question | Leetcode 384 | Shuffle an ArrayWorkWithGoogler · 8:25 · 3K views
384. Shuffle an Array (Leetcode Medium)Programming Live with Larry · 8:25 · 2K views
384. Shuffle an Array || leetcode || medium question || c++code Explainer · 4:13 · 1K views
LeetCode 384. Shuffle an Array Solution Explained - JavaAlgorithms and Data Structures Course · 9:05 · 843 views
384. Shuffle an Array | DESIGN SYSTEM | LEETCODE MEDIUMcode Explainer · 7:11 · 736 views
Daily Leetcode #476: Jul 20, 2021 - 384. Shuffle an ArrayProgramming Live with Larry · 8:12 · 324 views
384 Shuffle an Array | Medium Level Interview Question Solution in PythonEduEverybody · 6:48 · 250 views
Explain the Fisher Yates Algorithm and leetcode 384. Shuffle an ArrayMath Geeks · 8:04 · 166 views
384. Shuffle an Array | English | MediumSimple Code - 단순코드 · 4:33 · 118 views
The 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 arraynums.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]
Constraints:
1 <= nums.length <= 50-106 <= nums[i] <= 106- All the elements of
numsare unique. - At most
104calls in total will be made toresetandshuffle.
Approach overview
Problem Overview: Design a data structure that stores an integer array, supports resetting it to the original configuration, and returns a uniformly random permutation each time shuffle() is called.
Approach 1: Recursive Permutation Generation (O(n! * n) time, O(n) space)
This approach generates permutations of the array recursively and randomly selects one. At each recursion level, pick an element, append it to the current permutation, and recursively permute the remaining elements. Because there are n! possible permutations and building each permutation costs up to O(n), the total time becomes O(n! * n). While conceptually simple, it is extremely inefficient for larger arrays and not suitable for production or interview settings. The idea mainly demonstrates how permutations work using recursion on an array.
Approach 2: Fisher-Yates Shuffle Algorithm (O(n) time, O(1) space)
The Fisher-Yates algorithm produces a perfectly uniform random permutation in linear time. Iterate through the array from index 0 to n - 1. For each position i, generate a random index j between i and n - 1, then swap nums[i] and nums[j]. This ensures every element has an equal probability of appearing in each position. The algorithm runs in O(n) time and uses O(1) additional space since swaps occur in place. Random index generation uses concepts from math and randomized algorithms.
The class design stores two arrays: the original configuration and a working copy used for shuffling. The reset() operation simply returns the original array or restores the working copy from it. Each call to shuffle() performs the Fisher-Yates process on the working array to produce a new random ordering.
Recommended for interviews: Interviewers expect the Fisher-Yates shuffle. It demonstrates understanding of uniform random permutations and in-place algorithms. Mentioning permutation generation shows baseline understanding, but the linear-time Fisher-Yates approach signals strong knowledge of randomized algorithm design.
Approach 1: Fisher-Yates Shuffle Algorithm
The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient algorithm for generating a random permutation of a finite sequence. The algorithm works by iterating backward through the array and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet.
import random
class Solution:
def __init__(self, nums: List[int]):
self.original = nums[:]
self.array = nums[:]
def reset(self) -> List[int]:
self.array = self.original[:]
return self.array
def shuffle(self) -> List[int]:
for i in range(len(self.array) - 1, 0, -1):
j = random.randint(0, i)
self.array[i], self.array[j] = self.array[j], self.array[i]
return self.arrayimport java.util.Random;
class Solution {
private int[] original;
private int[] array;
private Random rand;
public Solution(int[] nums) {
original = nums.clone();
array = nums.clone();
rand = new Random();
}
public int[] reset() {
array = original.clone();
return array;
}
public int[] shuffle() {
for (int i = array.length - 1; i > 0; --i) {
int j = rand.nextInt(i + 1);
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
}#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
class Solution {
private:
std::vector<int> original;
std::vector<int> array;
public:
Solution(std::vector<int>& nums) : original(nums), array(nums) {
std::srand(std::time(0));
}
std::vector<int> reset() {
array = original;
return array;
}
std::vector<int> shuffle() {
for (int i = array.size() - 1; i > 0; --i) {
int j = std::rand() % (i + 1);
std::swap(array[i], array[j]);
}
return array;
}
};class Solution {
constructor(nums) {
this.original = nums.slice();
this.array = nums.slice();
}
reset() {
this.array = this.original.slice();
return this.array;
}
shuffle() {
for (let i = this.array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
[this.array[i], this.array[j]] = [this.array[j], this.array[i]];
}
return this.array;
}
}#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Solution {
int* original;
int* array;
int size;
} Solution;
Solution* solutionCreate(int* nums, int size) {
Solution* obj = (Solution*)malloc(sizeof(Solution));
obj->original = (int*)malloc(size * sizeof(int));
obj->array = (int*)malloc(size * sizeof(int));
obj->size = size;
for (int i = 0; i < size; ++i) {
obj->original[i] = nums[i];
obj->array[i] = nums[i];
}
srand(time(NULL));
return obj;
}
int* solutionReset(Solution* obj, int* ret_size) {
for (int i = 0; i < obj->size; ++i) {
obj->array[i] = obj->original[i];
}
*ret_size = obj->size;
return obj->array;
}
int* solutionShuffle(Solution* obj, int* ret_size) {
for (int i = obj->size - 1; i > 0; --i) {
int j = rand() % (i + 1);
int temp = obj->array[i];
obj->array[i] = obj->array[j];
obj->array[j] = temp;
}
*ret_size = obj->size;
return obj->array;
}
void solutionFree(Solution* obj) {
free(obj->original);
free(obj->array);
free(obj);
}using System;
public class Solution {
private int[] original;
private int[] array;
private Random rand;
public Solution(int[] nums) {
original = (int[])nums.Clone();
array = (int[])nums.Clone();
rand = new Random();
}
public int[] Reset() {
array = (int[])original.Clone();
return array;
}
public int[] Shuffle() {
for (int i = array.Length - 1; i > 0; i--) {
int j = rand.Next(i + 1);
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
}The Python implementation uses list slicing to copy arrays. The 'shuffle' function deploys Fisher-Yates algorithm by swapping the current index element with a randomly selected index element. The 'reset' function simply returns a fresh slice of the original.
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
Approach 2: Recursive Permutation Generation
This approach involves generating a permutation recursively by picking an element and placing it at different positions. This is less efficient than the Fisher-Yates method and not suitable for large arrays.
from random import randint
class Solution:
def __init__(self, nums: List[int]):
self.original = nums[:]
def reset(self) -> List[int]:
return self.original[:]
def shuffle(self) -> List[int]:
ans = self.original[:]
self._permute(ans, 0)
return ans
def _permute(self, lst, start):
if start == len(lst):
return lst
swap_idx = randint(start, len(lst) - 1)
lst[start], lst[swap_idx] = lst[swap_idx], lst[start]
self._permute(lst, start + 1)class Solution {
constructor(nums) {
this.original = nums.slice();
}
reset() {
return this.original.slice();
}
shuffle() {
let arr = this.original.slice();
this.permute(arr, 0);
return arr;
}
permute(arr, start) {
if (start >= arr.length) return;
let randIndex = Math.floor(Math.random() * (arr.length - start)) + start;
[arr[start], arr[randIndex]] = [arr[randIndex], arr[start]];
this.permute(arr, start + 1);
}
}In this Python solution, we recursively generate a permutation by swapping the current element with any element after it. This ensures that all permutations are equally probable, though it's less efficient for large arrays compared to Fisher-Yates.
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
Approach 3: Default Approach
class Solution {
private nums: number[];
constructor(nums: number[]) {
this.nums = nums;
}
reset(): number[] {
return this.nums;
}
shuffle(): number[] {
const n = this.nums.length;
const res = [...this.nums];
for (let i = 0; i < n; i++) {
const j = Math.floor(Math.random() * n);
[res[i], res[j]] = [res[j], res[i]];
}
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/type Solution struct {
nums, original []int
}
func Constructor(nums []int) Solution {
return Solution{nums, append([]int(nil), nums...)}
}
func (this *Solution) Reset() []int {
copy(this.nums, this.original)
return this.nums
}
func (this *Solution) Shuffle() []int {
n := len(this.nums)
for i := range this.nums {
j := i + rand.Intn(n-i)
this.nums[i], this.nums[j] = this.nums[j], this.nums[i]
}
return this.nums
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.Reset();
* param_2 := obj.Shuffle();
*/use rand::Rng;
struct Solution {
nums: Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl Solution {
fn new(nums: Vec<i32>) -> Self {
Self { nums }
}
fn reset(&self) -> Vec<i32> {
self.nums.clone()
}
fn shuffle(&mut self) -> Vec<i32> {
let n = self.nums.len();
let mut res = self.nums.clone();
for i in 0..n {
let j = rand::thread_rng().gen_range(0, n);
res.swap(i, j);
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Fisher-Yates Shuffle Algorithm | Time Complexity: O(n) for both reset and shuffle functions. |
| Recursive Permutation Generation | Time Complexity: O(n!) because it attempts every permutation recursively. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Permutation Generation | O(n! * n) | O(n) | Conceptual understanding of permutations or recursion |
| Fisher-Yates Shuffle | O(n) | O(1) | Standard approach for uniformly shuffling arrays in interviews and production |
Frequently asked questions
Is Shuffle an Array easy or hard?
Shuffle an Array is considered a medium difficulty problem. The design aspect of maintaining the original array and implementing a uniform shuffle requires knowledge of the Fisher-Yates algorithm and basic randomized techniques.
Shuffle an Array Python/Java solution
Most implementations follow the same structure: store the original array, copy it when needed, and apply the Fisher-Yates shuffle during the shuffle() method. Python uses the random module, while Java commonly uses java.util.Random or ThreadLocalRandom.
How to solve Shuffle an Array in O(n)?
Use the Fisher-Yates shuffle. Iterate from index 0 to n-1, generate a random index j between i and n-1, and swap nums[i] with nums[j]. This guarantees every permutation appears with equal probability and completes in linear O(n) time.
What is the best approach for Shuffle an Array?
The Fisher-Yates shuffle algorithm is the best approach. It iterates through the array and swaps each element with a randomly chosen element from the remaining positions. This produces a perfectly uniform random permutation in O(n) time and O(1) extra space, making it the standard solution expected in interviews.
Is Shuffle an Array asked at Google/Amazon/Meta?
Shuffle and randomization problems appear frequently at companies like Google, Amazon, and Meta because they test understanding of probability, randomness, and algorithm design. Fisher-Yates is a classic algorithm many interviewers expect candidates to recognize.
What data structure is used in Shuffle an Array?
The primary data structure is an array. The class typically stores two arrays: the original configuration and a working array used for shuffling. Random index generation combined with array swapping implements the Fisher-Yates algorithm efficiently.
What is the time complexity of Shuffle an Array?
Using the Fisher-Yates algorithm, the shuffle operation runs in O(n) time because each element is visited exactly once and swapped with a randomly chosen index. Space complexity is O(1) since the algorithm performs swaps in place without extra memory beyond the stored original array.