{x}
blog image

Shuffle an Array

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]

 

Constraints:

  • 1 <= nums.length <= 50
  • -106 <= nums[i] <= 106
  • All the elements of nums are unique.
  • At most 104 calls in total will be made to reset and shuffle.

Solution Explanation for Shuffle an Array

This problem requires designing a data structure that can efficiently shuffle an array and reset it to its original state. The core idea is to use Fisher-Yates (Knuth) shuffle algorithm for randomization.

Algorithm:

  1. Initialization (__init__ / constructor): The constructor takes the input array nums and stores a copy of it as original to enable resetting.

  2. Reset (reset): This method simply returns a copy of the original array, restoring the array to its initial state.

  3. Shuffle (shuffle): This is where the Fisher-Yates shuffle is implemented. The algorithm iterates through the array from the end. For each element at index i, it randomly selects an element from the remaining unshuffled portion of the array (indices i to the end) and swaps them. This ensures that every permutation is equally likely.

Fisher-Yates Shuffle (Knuth Shuffle):

The core idea behind the Fisher-Yates shuffle is to iterate through the array from the end. For each index i, it randomly selects an index j from i to the end of the array. It then swaps the elements at indices i and j. This process ensures that each element has an equal chance of ending up in any position.

Code Explanation (Python as Example):

import random
class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums.copy()
 
    def reset(self) -> List[int]:
        self.nums = self.original.copy()
        return self.nums
 
    def shuffle(self) -> List[int]:
        for i in range(len(self.nums)):
            j = random.randrange(i, len(self.nums))
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums
  • __init__(self, nums): Initializes the object with the input array nums and creates a copy original.
  • reset(self): Copies original back to nums and returns the copy.
  • shuffle(self): Implements the Fisher-Yates shuffle. random.randrange(i, len(self.nums)) selects a random index j from i to the end of the array (inclusive). The elements at indices i and j are then swapped.

Time Complexity Analysis:

  • __init__: O(N), where N is the length of the input array, due to creating a copy.
  • reset: O(N) due to copying the original array.
  • shuffle: O(N) because the algorithm iterates through the array once.

Space Complexity Analysis:

  • O(N) to store the original array and the shuffled array.

The provided solutions in other languages (Java, C++, Go, TypeScript, Rust, JavaScript) follow the same logic and algorithm, differing only in syntax and library usage for random number generation and array handling. The time and space complexity remain consistent across all implementations.