# sort
#  - time: O(nlogn)
#  - space: O(1)/O(n)
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        res = 0
        nums.sort()
        
        curr, streak = nums[0], 0
        i = 0
        while i < len(nums):
            if curr != nums[i]:
                curr = nums[i]
                streak = 0
            while i < len(nums) and nums[i] == curr:
                i += 1
            streak += 1
            curr += 1
            res = max(res, streak)
        return res
      
# hashmap
#  - time: O(n)
#  - space: O(n)
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m = set()
        for num in nums:
            m.add(num)

        res = 0
        for num in m:  # 而不是 for loop nums，因为 num 可能会重复，因而 for loop nums 可能会执行重复的同样元素
            if num - 1 not in m:  # 表明 num 是一个 consecutive sequence 的起始元素
                cur = 1
                while num + cur in m:
                    cur += 1
                res = max(res, cur)
        return res

# brute force
#  Time complexity: O(n2)
#  Space complexity: O(1)
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

# sort
 - Time complexity: O(nlogn)
 - Space complexity: O(1)/O(n)
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False
      
# hashmap      
 - Time complexity: O(n)
 - Space complexity: O(n)
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""

	my_set = set()
	for num in nums:
		if num in my_set:
			return True
		my_set.add(num)
	return False

# sorting
#  Time complexity: O(nlogn)
#  Space complexity: O(n)
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res

# heap
#  Time complexity: O(nlogk)
#  Space complexity: O(n + k)
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res     
      
# bucket sort + hashmap
#  Time complexity: O(n)
#  Space complexity: O(n)
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1

        buckets = [[] for i in range(len(nums) + 1)] # why range(len(nums) + 1，因为最极端的情况（如果 nums 里只有一种元素），则该元素的数量等于 len(nums)
        for num, count in counts.items():
            buckets[count].append(num)

        res = []
        for i in range(len(buckets) - 1, 0, -1): # time: O(n)
            res.extend(buckets[i])
            if len(res) == k:
                return res