'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from itertools import permutations 
import random


class Solution1:
    # Fisher-Yates 
    # T and T: O(n), generating a random index and swapping two values 
    # can be done in constant time
    def __init__(self, nums):
        self.array = nums
        self.original = list(nums)

    def reset(self):
        self.array = self.original
        self.original = list(self.original)
        return self.array

    def shuffle(self):
        for i in range(len(self.array)):
            swap_idx = random.randrange(i, len(self.array))
            self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
        return self.array
    


class Solution:

    def __init__(self, nums: List[int]):
        self.array = nums
        self.original = list(nums)

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        self.array = self.original # these two are in the same memory
        self.original = list(self.original) # deep copy, i.e., self.original = self.original[:]
        return self.array
        
    # O(n^2), pop is O(n)
    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        tmp = list(self.array)
        
        for idx in range(len(tmp)):
            remove_idx = random.randrange(len(tmp))
            self.array[idx] = tmp.pop(remove_idx) # pop(idx) means poping the 
        return self.array
            
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()