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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shuffle an Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires a uniform random shuffle of an array, which can be achieved using the Fisher-Yates shuffle algorithm.
  • The reset function should restore the array to its original state, which requires storing the initial array.
  • Given the constraints, we need to ensure that our solution is efficient and handles up to 10,000 calls to shuffle and reset.

Space and Time Complexity

Time Complexity:

  • reset: O(n), where n is the length of the array (copying the original array).
  • shuffle: O(n), as we iterate through the array to swap elements.

Space Complexity:

  • O(n) for storing the original array.

Solution

To solve the problem, we will utilize an array to store the original configuration of the input array. The Fisher-Yates algorithm will be used in the shuffle method, which ensures that each permutation of the array is equally likely. This is achieved by iterating from the last index to the beginning and swapping each element with a randomly selected element that comes before it (including itself).

Code Solutions

import random

class Solution:
    def __init__(self, nums: List[int]):
        self.original = nums[:]  # Store the original array
        self.nums = nums[:]      # Copy the original array for shuffling

    def reset(self) -> List[int]:
        self.nums = self.original[:]  # Reset to original configuration
        return self.nums

    def shuffle(self) -> List[int]:
        for i in range(len(self.nums) - 1, 0, -1):
            j = random.randint(0, i)  # Get a random index
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]  # Swap
        return self.nums
← Back to All Questions