Introduction

In this blog post, we will explore how to solve the LeetCode problem "384" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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] 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.

Explanation

• Initialization: Store a copy of the original array to allow resetting.
  • Shuffle (Fisher-Yates): Implement the Fisher-Yates shuffle algorithm in-place to ensure each permutation has an equal probability. Iterate through the array, swapping each element with a randomly chosen element from the remaining unsorted portion.
  • Reset: Return the stored original array.

• Time Complexity: O(n) for both shuffle and reset, where n is the length of the array. Space Complexity: O(n) due to storing the original array.

Code

    import random

class Solution:
    def __init__(self, nums):
        self.original = list(nums)  # Store a copy to reset
        self.nums = nums

    def reset(self):
        """
        Resets the array to its original configuration and returns it.
        """
        self.nums = list(self.original)
        return self.nums

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        """
        n = len(self.nums)
        for i in range(n):
            # Pick a random index from i to n-1
            j = random.randrange(i, n)
            # Swap arr[i] with the element at random index
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums