Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
• It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

Solution

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Time complexity: O(n)
        # Space complexity: O(n)
        
        bag = {}
        for elt in nums:
            if elt not in bag:
                bag[elt] = 1
            else:
                bag[elt] += 1
        
        # Index of array = frequencies
        freq = [[] for i in range(len(nums) + 1)]
        
        for key, val in bag.items():
            freq[val].append(key)
        
        res = []
        i, n = 0, len(freq)
        
        while i < n and k != 0:
            if len(freq[n-1-i]) > 0:
                res += freq[n-1-i]
                k -= len(freq[n-1-i])
            i += 1
            
        return res

Solution 1: Priority Queue using Heap

class Solution:
    import heapq 
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # N = # of elt in nums
        # k = size of heap.
        # Time complexity: O(Nlog(k)).
        # Space complexity: O(N+k)
        
        # 1. build hash map : character and how often it appears
        # O(N) time
        hashmap = {}
        for elt in nums:
            if elt in hashmap:
                hashmap[elt] += 1
            else:
                hashmap[elt] = 1
        # 2-3. build heap of top k frequent elements and
        # convert it into an output array
        # O(N log k) time
        return heapq.nlargest(k, hashmap.keys(), key=hashmap.get)

Solution 2: Using divide and conquer approach (quicksort like)

• Doesn't seem to work on a very large amount of numbers. Investigate why:
  https://leetcode.com/problems/top-k-frequent-elements/discuss/685786/why-is-my-code-not-working-on-the-very-last-test-case-huge-one

class Solution:
    def partition(self, L, frequency, lo, hi, k):    
        if len(L) == k:
            return L
        else:
            pivot, i, j = lo, lo, hi
            while i < j:
                while i < hi and frequency[L[i]] <= frequency[L[pivot]]:
                    i += 1
                while j > lo and frequency[L[j]] >= frequency[L[pivot]]:
                    j -= 1
                if i < j:
                    L[i], L[j] = L[j], L[i] 
                    
            L[pivot], L[j] = L[j], L[pivot]
            rightPart = L[pivot+1:]
            return self.partition(rightPart, frequency, 0, len(rightPart)-1, k)
        
    
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # N = # of elt in nums
        # k = size of heap.
        # Time complexity: O(N).
        # Space complexity: O(N)
        
        # 1. build hash map : character and how often it appears
        #    and array of unique elements.
        # O(N) time
        hashmap = {}
        unq_elts = []
        for elt in nums:
            if elt in hashmap:
                hashmap[elt] += 1
            else:
                hashmap[elt] = 1
                unq_elts.append(elt)
                
        # 2. Choose a random pivot and put it in its place in a sorted array
        rightPart = self.partition(unq_elts, hashmap, 0, len(unq_elts)-1, k)
        
        # 3. Return the k most frequent elements from the right part array.
        return rightPart