NUHMAN.com

📘 Problem Statement

Given an integer array nums, design an algorithm that will randomly shuffle the array and return it. Implement the Solution class:

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

📚 Example:

python

Input:
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output:
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

🧠 Key Insight

This problem asks us to design a solution for random shuffling. The naive approach would be to manually swap the elements in the array, but we want an efficient and random solution. The problem can be solved using the Fisher-Yates Shuffle Algorithm (also known as Knuth Shuffle), which ensures an unbiased shuffle of the array.

💡 Approach

1. Initialization:

• When we instantiate the Solution object, we store the original array to facilitate easy resetting.

1. Shuffling:

• The Fisher-Yates Shuffle Algorithm is used to randomly shuffle the array. The idea is to iterate through the array and, for each element, randomly swap it with any element that comes after it (including itself).

1. Reset:

• The reset() method simply returns the array to its original state.

🐍 Python Code

python

import random

class Solution:
    def __init__(self, nums: list[int]):
        """
        Initializes the Solution object with the original array.
        """
        self.original = nums  # Store the original array
        self.nums = nums[:]   # Make a copy of the array for shuffling
    
    def reset(self) -> list[int]:
        """
        Resets the array to its original configuration and returns it.
        """
        self.nums = self.original[:]  # Reset the array to original
        return self.nums
    
    def shuffle(self) -> list[int]:
        """
        Returns a random shuffling of the array.
        """
        random.shuffle(self.nums)  # Use random.shuffle to shuffle the array in-place
        return self.nums

🔍 Step-by-Step Explanation

1. Initialization (__init__ Method)

python

def __init__(self, nums: list[int]):
    self.original = nums  # Store the original array
    self.nums = nums[:]   # Make a copy of the array for shuffling

• We initialize the object with the given array nums. We store a copy of the original array, so we can reset it later without modifying the original array during shuffling.

2. Reset (reset Method)

python

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

• The reset() method restores the array to its original configuration by copying the original array back into the nums array and returning it.

3. Shuffle (shuffle Method)

python

def shuffle(self) -> list[int]:
    random.shuffle(self.nums)  # Shuffle the array in place
    return self.nums

• The shuffle() method uses Python's built-in random.shuffle() to randomly shuffle the array nums. This function performs an in-place shuffle of the array, ensuring that all permutations of the array are equally likely.

💡 Example Walkthrough

Example 1:

python

Input:
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output:
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

1. Solution Initialization: ["Solution", [1, 2, 3]]

• The object is initialized with the array [1, 2, 3].

1. Shuffle: The shuffle() function shuffles the array. One possible output could be [3, 1, 2] (the shuffle is random).
2. Reset: The reset() function restores the array to its original state, [1, 2, 3].
3. Shuffle Again: Another shuffle happens, and the output could be [1, 3, 2] (again, the result is random).

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n) for shuffle, O(n) for resetSpace ComplexityO(n) for storing the array

• Time Complexity:
• The shuffle() function has a time complexity of O(n), where n is the number of elements in the array. This is because random.shuffle() performs a linear pass over the array.
• The reset() function is O(n) since we create a copy of the original array when resetting.
• Space Complexity:
• We use O(n) space to store the original array, as well as the shuffled array. Therefore, the space complexity is O(n).

🧵 Final Thoughts

LeetCode 384 is an excellent exercise in implementing a randomized algorithm. By using the Fisher-Yates Shuffle Algorithm, we ensure that the shuffle is unbiased and efficient. Python’s random.shuffle() provides a simple way to implement this efficiently. Additionally, the reset() method ensures that we can revert back to the original array state at any time.

This problem is a great demonstration of array manipulation, shuffling algorithms, and working with Python’s built-in libraries effectively.