We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shuffle an Array

Number: 384

Difficulty: Medium

Paid? No

Companies: LinkedIn, Uber, Microsoft, Google, Meta, Nvidia

Problem Description

Given an integer array nums, design an algorithm to randomly shuffle the array. Ensure that every permutation of the array is equally likely to be returned by the shuffle method. The class should also provide a reset function that returns the array to its original configuration.

Key Insights

  • Use the Fisher-Yates (Knuth) shuffle algorithm to achieve an unbiased shuffle.
  • Save the original configuration of the array to allow for a reset.
  • The Fisher-Yates algorithm works by iterating over the array and swapping each element with another randomly chosen element.

Space and Time Complexity

Time Complexity: O(n) for both shuffling and resetting the array. Space Complexity: O(n) due to storing a copy of the original array.

Solution

We store a copy of the initial array to enable resetting. The shuffle method uses the Fisher-Yates algorithm. For each index i from the beginning to the end of the array, we choose a random index between i and the end of the array and swap the elements at indices i and the chosen index. This method ensures every permutation is equally likely.

Code Solutions

import random

class Solution:
    def __init__(self, nums):
        # Save the original array configuration
        self.original = nums[:]
        self.nums = nums[:]

    def reset(self):
        # Reset the array to its original configuration by making a copy
        self.nums = self.original[:]
        return self.nums

    def shuffle(self):
        # Implement Fisher-Yates shuffle
        n = len(self.nums)
        for i in range(n):
            # Pick a random index from i to n-1
            rand_index = random.randint(i, n-1)
            # Swap elements at positions i and rand_index
            self.nums[i], self.nums[rand_index] = self.nums[rand_index], self.nums[i]
        return self.nums
← Back to All Questions