# Solution For Shuffle An Array

Problem Statement:

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]

Solution:

Approach 1:

The simplest approach would be to shuffle the array randomly every time the shuffle method is called. This can be achieved by using the Fisher-Yates shuffle algorithm, which works in O(n) time complexity.

Algorithm:

1. Create an array called shuffledArray of length n, where n is the length of the input array nums.
2. Copy the contents of nums into shuffledArray.
3. For i from n – 1 to 1:
a. Generate a random integer j between 0 and i inclusive.
b. Swap the values in shuffledArray at indices i and j.
4. Return shuffledArray when shuffle method is called. Return copied array nums when reset method is called.

Time Complexity:

The time complexity of this approach is O(n) for every shuffle, as we are iterating over the array once for each shuffle. The time complexity of the reset method is O(n) as it involves copying the original array once.

Space Complexity:

The space complexity of this approach is O(n) as we are using an extra array to store the shuffled input array.

Code:

public class Solution {
private int[] originalArray;
private int[] shuffledArray;
private Random random;

``````public Solution(int[] nums) {
originalArray = nums;
shuffledArray = Arrays.copyOf(nums, nums.length);
random = new Random();
}

/** Resets the array to its original configuration and return it. */
public int[] reset() {
shuffledArray = Arrays.copyOf(originalArray, originalArray.length);
return shuffledArray;
}

/** Returns a random shuffling of the array. */
public int[] shuffle() {
for (int i = shuffledArray.length - 1; i >= 1; i--) {
int j = random.nextInt(i + 1);
swap(shuffledArray, i, j);
}
return shuffledArray;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
``````

}

Approach 2:

A more space-efficient approach is to not use an extra array to store the shuffled input array. Instead, we can modify the input array in place and shuffle it randomly using the Fisher-Yates shuffle algorithm.

Algorithm:

1. For i from n – 1 to 1:
a. Generate a random integer j between 0 and i inclusive.
b. Swap the values in nums at indices i and j.
2. Return nums when shuffle method is called. Return copied array nums when reset method is called.

Time Complexity:

The time complexity of this approach is O(n) for every shuffle, as we are iterating over the array once for each shuffle. The time complexity of the reset method is O(n) as it involves copying the original array once.

Space Complexity:

The space complexity of this approach is O(1) as we are modifying the input array in place. No extra space is used.

Code:

public class Solution {
private int[] originalArray;
private Random random;

``````public Solution(int[] nums) {
originalArray = nums;
random = new Random();
}

/** Resets the array to its original configuration and return it. */
public int[] reset() {
return originalArray;
}

/** Returns a random shuffling of the array. */
public int[] shuffle() {
int[] shuffledArray = Arrays.copyOf(originalArray, originalArray.length);

for (int i = shuffledArray.length - 1; i >= 1; i--) {
int j = random.nextInt(i + 1);
swap(shuffledArray, i, j);
}
return shuffledArray;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
``````

}

## Step by Step Implementation For Shuffle An Array

```class Solution {
public int[] shuffle(int[] nums, int n) {
int[] result = new int[2 * n];
int index = 0;
for (int i = 0; i < n; i++) {
result[index] = nums[i];
index++;
result[index] = nums[i + n];
index++;
}
return result;
}
}```
```class Solution:
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
self.original = list(nums)

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
self.nums = self.original
self.original = list(self.original)
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
for i in range(len(self.nums)):
swap_idx = random.randrange(i, len(self.nums))
self.nums[i], self.nums[swap_idx] = self.nums[swap_idx], self.nums[i]

return self.nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()```
```/**
* @param {number[]} nums
* @return {number[]}
*/
var shuffle = function(nums) {
};```
```class Solution {
public:
Solution(vector& nums) {
this->nums = nums;
}

/** Resets the array to its original configuration and return it. */
vector reset() {
return nums;
}

/** Returns a random shuffling of the array. */
vector shuffle() {
vector shuffled(nums);
for (int i = 0; i < shuffled.size(); i++) {
int j = rand() % (i + 1);
swap(shuffled[i], shuffled[j]);
}
return shuffled;
}

private:
vector nums;
};

/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector param_1 = obj->reset();
* vector param_2 = obj->shuffle();
*/```
```public class Solution {
public int[] Shuffle(int[] nums, int n) {
//Create a new array to store the shuffled elements
int[] shuffled = new int[2 * n];

//Fill the new array with the shuffled elements
for(int i = 0; i < n; i++)
{
shuffled[2 * i] = nums[i];
shuffled[(2 * i) + 1] = nums[i + n];
}

return shuffled;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]