algoadvance

Leetcode 384. Shuffle an Array

Problem Statement

You need to design a class to shuffle a given array and also be able to reset it to its original configuration. Imagine this functionality as two operations: “shuffle” and “reset”.

Implement the Solution class:

Clarifying Questions

Before jumping into the solution, it’s important to clarify the requirements:

  1. Is the array guaranteed to have at least one element?
    • Typically, yes, but handle edge cases with zero or one element.
  2. Should the shuffle be uniformly random?
    • Yes, each permutation should be equally likely.
  3. Can I use built-in random functions?
    • Yes, using C++ standard library functions like std::random_shuffle.

Strategy

  1. Store the Original Configuration:
    • Maintain a copy of the original array so that we can reset to the exact original.
  2. Shuffle Using Fisher-Yates Algorithm:
    • Fisher-Yates provides an efficient way to generate a random permutation of an array where all permutations are equally likely.

Code Implementation

Here’s how you can implement this in C++:

#include <vector>
#include <algorithm>  // for std::swap
#include <random>     // for std::default_random_engine
#include <ctime>      // for std::time

class Solution {
private:
    std::vector<int> original;
    std::vector<int> array;

public:
    Solution(std::vector<int>& nums) : original(nums), array(nums) {
        // Seed the random number generator
        std::srand(unsigned(std::time(0)));
    }
    
    std::vector<int> reset() {
        array = original;
        return array;
    }
    
    std::vector<int> shuffle() {
        int n = array.size();
        // Fisher-Yates Shuffle Algorithm
        for (int i = n - 1; i > 0; --i) {
            int j = std::rand() % (i + 1);
            std::swap(array[i], array[j]);
        }
        return array;
    }
};

Explanation

  1. Initialization (Solution(std::vector<int>& nums)):
    • Store both the original and current arrays.
    • Seed the random number generator.
  2. Reset (reset()):
    • Simply copy the original array back to the current array and return it.
  3. Shuffle (shuffle()):
    • Implementing a Fisher-Yates shuffle to ensure a uniform random permutation.
    • Iterate in reverse order, swapping elements with randomly chosen positions.

Time Complexity

Both operations reset and shuffle are efficient:

  1. Reset Time Complexity: ( O(n) )
    • Reset requires copying the array which takes linear time relative to the size of the array.
  2. Shuffle Time Complexity: ( O(n) )
    • Fisher-Yates algorithm runs in linear time, with each swap being ( O(1) ).

Thus, the overall performance is optimal for the given operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI