Leetcode 384. Shuffle an Array
Problem Explanation
The problem is asking us to create a data structure that would shuffle a provided list of integers. This data structure should have two operations:
shuffle
: It rearranges the elements in the list in a random manner. Every permutation of the list should be equally likely to be chosen.reset
: It reverts the list back to its original state.
For instance, if we initiate the program with the list [1, 2, 3]
, calling the shuffle
function may return [2, 1, 3]
, [3, 1, 2]
, or any other permutation of the list. Calling the reset
function after that should return the original list [1, 2, 3]
.
Solution Approach
To solve this problem, we can use the Fisher-Yates algorithm. The basic idea of this algorithm is to iterate through the list from the last element to the first. For each element, we randomly select an index from 0 to the current index. We then swap this element with the element at the randomly selected index. This gives us a random permutation of the list.
Steps of the Algorithm:
Let's take an example of the list a = [1, 2, 3, 4, 5]
.
- We start from index 4 (the last index), and generate a random index
r
between 0 and 4. - Let's say
r
is 2. We swap the elements at indices 4 and 2. The list becomesa = [1, 2, 5, 4, 3]
. - We move to the next index, 3, and again generate a random index
r
between 0 and 3. - Let's say
r
is 1. We swap the elements at indices 3 and 1. The list becomesa = [1, 4, 5, 2, 3]
. - We continue this process until we reach the first element of the list.
Solutions
Python Solution
1 2python 3import random 4 5class Solution: 6 def __init__(self, nums): 7 self.nums = nums 8 self.original = nums.copy() 9 10 def reset(self): 11 self.nums = self.original.copy() 12 return self.nums 13 14 def shuffle(self): 15 for i in range(len(self.nums) - 1, 0, -1): 16 j = random.randint(0, i) 17 self.nums[i], self.nums[j] = self.nums[j], self.nums[i] 18 return self.nums
Here, the __init__
method initializes the Solution object with a copy of the given list. The reset
method reverts the list to its original state by again assigning to it the copy made during initialization. The shuffle
method rearranges the list in a random manner according to the Fisher-Yates algorithm.
Java Solution
1 2java 3import java.util.Random; 4import java.util.Arrays; 5 6public class Solution { 7private int[] nums; 8private int[] original; 9 10public Solution(int[] nums) { 11 this.nums = nums; 12 this.original = nums.clone(); 13} 14 15public int[] reset() { 16 this.nums = this.original; 17 this.original = original.clone(); 18 return nums; 19} 20 21public int[] shuffle() { 22 Random rand = new Random(); 23 for (int i = 1; i < nums.length; i++) { 24 int j = rand.nextInt(i + 1); 25 swap(nums, i, j); 26 } 27 return nums; 28} 29 30private void swap(int[] nums, int i, int j) { 31 int temp = nums[i]; 32 nums[i] = nums[j]; 33 nums[j] = temp; 34} 35}
This Java solution is very similar to the Python solution. We use arrays for the list of integers, and we use the clone
function to copy arrays.
JavaScript Solution
1
2javascript
3class Solution {
4 constructor(nums) {
5 this.nums = nums;
6 this.original = [...nums];
7 }
8
9 reset() {
10 this.nums = [...this.original];
11 return this.nums;
12 }
13
14 shuffle() {
15 for (let i = this.nums.length - 1; i > 0; i--) {
16 let j = Math.floor(Math.random() * (i + 1));
17 [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
18 }
19 return this.nums;
20 }
21}
In JavaScript, we use the spread operator (...
) to copy arrays. The rest of the code is almost the same as in the Python and Java solutions.
C++ Solution
1
2c++
3#include <vector>
4#include <random>
5
6class Solution {
7private:
8std::vector<int> nums, original;
9
10void swap(int i, int j) {
11 int temp = nums[i];
12 nums[i] = nums[j];
13 nums[j] = temp;
14}
15
16public:
17Solution(std::vector<int>& nums) : nums(nums), original(nums) {}
18
19std::vector<int> reset() {
20 nums = original;
21 return nums;
22}
23
24std::vector<int> shuffle() {
25 for (int i = nums.size() - 1; i > 0; i--) {
26 int j = rand() % (i + 1);
27 swap(i, j);
28 }
29 return nums;
30}
31};
The C++ solution is similar to the Java solution, but now we use the vector
class for the list of integers.
C# Solution
1 2csharp 3 4public class Solution 5{ 6private int[] nums; 7private int[] original; 8 9public Solution(int[] nums) 10{ 11 this.nums = nums; 12 this.original = (int[])nums.Clone(); 13} 14 15public int[] Reset() 16{ 17 nums = (int[])original.Clone(); 18 return nums; 19} 20 21public int[] Shuffle() 22{ 23 Random rand = new Random(); 24 for (int i = 0; i < nums.Length; i++) 25 { 26 int j = rand.Next(i, nums.Length); 27 int temp = nums[i]; 28 nums[i] = nums[j]; 29 nums[j] = temp; 30 } 31 return nums; 32} 33}
The C# solution is similar to the Java solution. The Clone
method is used to copy an array to a new variable.## Kotlin Solution
1
2kotlin
3import kotlin.random.Random
4
5class Solution(nums: IntArray) {
6 private val original = nums.clone()
7 private val numsArray = nums.clone()
8
9 fun reset(): IntArray {
10 return original.clone()
11 }
12
13 fun shuffle(): IntArray {
14 for (i in numsArray.indices.reversed()) {
15 val j = Random.nextInt(i + 1)
16 val temp = numsArray[i]
17 numsArray[i] = numsArray[j]
18 numsArray[j] = temp
19 }
20 return numsArray.clone()
21 }
22}
In this Kotlin solution, the clone()
function is used to copy the original array to a new variable. Like the other solutions, the algorithm follows the Fisher-Yates shuffle - but in this case, Random.nextInt(i + 1)
is used to get the random index j
.
Swift Solution
1
2swift
3import Foundation
4
5class Solution {
6 private let array: [Int]
7 private var shuffled: [Int]
8
9 init(_ nums: [Int]) {
10 array = nums
11 shuffled = nums
12 }
13
14 func reset() -> [Int] {
15 shuffled = array
16 return shuffled
17 }
18
19 func shuffle() -> [Int] {
20 for i in stride(from: shuffled.count - 1, through: 1, by: -1) {
21 let j = Int.random(in: 0...i)
22 shuffled.swapAt(i, j)
23 }
24 return shuffled
25 }
26}
In Swift, we use the stride(from:through:by:)
method to do the reverse loop operation. Int.random(in: 0...i)
is used to generate the random index j
and shuffle.swapAt(i, j)
is used for swapping the elements.
Typescript Solution
1
2typescript
3class Solution {
4 original:Array<number>;
5 nums:Array<number>;
6
7 constructor(nums:Array<number>) {
8 this.nums = nums;
9 this.original = [...nums];
10 }
11
12 shuffle() {
13 for (let i = this.nums.length - 1; i > 0; i--) {
14 const j = Math.floor(Math.random() * (i + 1));
15 [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
16 }
17 return this.nums;
18 }
19
20 reset() {
21 this.nums = [...this.original];
22 return this.nums;
23 }
24}
25
In this TypeScript solution, we use the spread ...
operator to copy the original array to a new variable. And for similarity, Math.random()
is used to create random numbers, which are then rounded down to the nearest integer using Math.floor()
. For swapping the values in JS/TS, the array destructuring method is the most popular one, [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]]
does that job perfectly.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.