algoadvance

Given an integer array nums, design an algorithm to randomly shuffle the array. Implement the Solution class with the following methods:

  1. Solution(int[] nums): Initializes the object with the integer array nums.
  2. int[] reset(): Resets the array to its original configuration and returns it.
  3. int[] shuffle(): Returns a random shuffling of the array.

Example:

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 randomly and return the result. Any permutation of [1, 2, 3] must be equally likely to be returned.
solution.reset();      // Resets the array to its original configuration [1, 2, 3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1, 2, 3]

Clarifying Questions

  1. Can we assume the input array will contain only integers, and there are no constraints on the size of the array?
    • Yes, you can assume that the input array contains only integers and there are no constraints on the size of the array.
  2. Is the randomness required to be uniform?
    • Yes, the shuffling should provide a uniform distribution.
  3. Can we use built-in methods for shuffling the array?
    • Yes, you can use built-in methods but be prepared to explain your approach in detail and provide a manual implementation if required.

Strategy

  1. Initialization (__init__ method):
    • Store the original array.
    • Create a copy for shuffling.
  2. Reset Method (reset):
    • Return the original configuration of the array.
  3. Shuffle Method (shuffle):
    • Use the Fisher-Yates algorithm (also known as the Knuth shuffle) for shuffling the array to ensure uniform distribution.
    • Swap each element with a randomly selected element from the rest of the array.

Code:

import random

class Solution:

    def __init__(self, nums: list[int]):
        self.original = nums[:]  # store the original array
        self.array = nums[:]     # create a mutable copy of the array

    def reset(self) -> list[int]:
        self.array = self.original[:]  # reset to original configuration
        return self.array

    def shuffle(self) -> list[int]:
        # Implementing Fisher-Yates shuffle
        for i in range(len(self.array)):
            swap_idx = random.randint(i, len(self.array) - 1)  # select a random index to swap with
            self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
        return self.array

Time Complexity

  1. Initialization (__init__ method):
    • Time complexity: O(n) where n is the number of elements in the array.
    • Space complexity: O(n) for storing the original and current array.
  2. Reset Method (reset):
    • Time complexity: O(n) because it needs to copy the array.
    • Space complexity: O(1) as we only mutate the existing array.
  3. Shuffle Method (shuffle):
    • Time complexity: O(n) as we iterate through the array once.
    • Space complexity: O(1) as we shuffle the array in place without additional memory.

The Fisher-Yates algorithm ensures that each possible permutation of the array is equally likely, fulfilling the requirement for uniform randomness.

Try our interview co-pilot at AlgoAdvance.com