# - solution 1 - buckle sort
# - time: O(n)
# - space: O(1)
# - we have 3 buckets, for 1, 2 and 3, respectively, and count the num appearing times or every bucket
	def sortColors(self, nums: List[int]) -> None:
		bucket = [0, 0, 0]
		for num in nums:
			bucket[num] += 1

		i = 0
		for num in range(len(bucket)):
			count = bucket[num]
			while count > 0:
				nums[i] = num # in-place modify
				i += 1
				count -= 1

# solution 2 - quick select
# - time: O(n)
# - space: O(1)
	def sortColors(self, nums: List[int]) -> None:
		p = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				nums[i], nums[p] = nums[p], nums[i]
				p += 1
    # after above, the elements before p are all 0
    
		for i in range(p, len(nums)):
			if nums[i] == 1:
				nums[i], nums[p] = nums[p], nums[i]
				p += 1
    # after above, the elements before p are all 1, except for the part 1 (all are 0)    

# solution 3 - quick sort
# - time: O(n)
# - space: O(1)
	def sortColors(self, nums: List[int]) -> None:
		l, r = 0, len(nums) - 1
		i = 0
		while i <= r:  # need to execute until i > r
			if nums[i] == 0:
				nums[i], nums[l] = nums[l], nums[i]  # so that the elements before l are 0
				l += 1
				i += 1
			elif nums[i] == 2:
				nums[i], nums[r] = nums[r], nums[i]  # so that the elements after r are 2
				r -= 1
			# should not call i+=1, otherwise a 1 may occur before i
			else:
				i += 1

# solution 1 - use hashmap
# time: O(n)
# space: O(n)
	def majorityElement(self, nums: List[int]) -> int:
		maxCount, res = 0, 0
		m = {}
		for num in nums:
			m[num] = 1 + m.get(num, 0)
			if m[num] > maxCount:
				res = num
			maxCount = max(maxCount, m[num])

		return res

# solution 2 - Boyer–Moore algo
# - use "The majority element is the element that appears more than ⌊n / 2⌋ times"

# solution 1 - brute force
class Solution:
	def __init__(self, nums: List[int]):
		self.nums = nums
		self.original = nums.copy()  # space: O(n)

	def reset(self) -> List[int]:
		self.nums = self.original.copy()  # space: O(n) if consider the space occupied by the return value
		return self.nums

	def shuffle(self) -> List[int]:
		shuffled = [0] * len(self.nums)
		for i in range(len(self.nums)):  # time: O(n^2)
			j = random.randrange(len(self.nums))  # randomly generate an index from nums
			shuffled[i] = self.nums.pop(j)  # insert into shuffled
		self.nums = shuffled
		return self.nums
  
# solution 2 - Fisher-Yates 洗牌算法  
class Solution:
	def __init__(self, nums: List[int]):
		self.nums = nums
		self.original = nums.copy()  # space: O(n)

	def reset(self) -> List[int]:
		self.nums = self.original.copy()  # space: O(n) if consider the space occupied by the return value
		return self.nums

	def shuffle(self) -> List[int]:
		for i in range(len(self.nums)):  # time: O(n)
			j = random.randrange(i, len(self.nums))  # randomly generate an index from [i, len(nums]-1]
			self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
		return self.nums