<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k</code> <em>most frequent elements</em>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,1,1,2,2,3], k = 2
<strong>Output:</strong> [1,2]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1], k = 1
<strong>Output:</strong> [1]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
	<li><code>k</code> is in the range <code>[1, the number of unique elements in the array]</code>.</li>
	<li>It is <strong>guaranteed</strong> that the answer is <strong>unique</strong>.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Your algorithm&#39;s time complexity must be better than <code>O(n log n)</code>, where n is the array&#39;s size.</p>

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
                # 09/16/24 meta phone screen prep
        cnt = defaultdict(int)
        for n in nums:
            cnt[n] += 1
        nums_cnts = [(cnt[n], n) for n in cnt ]

        def quickSelect(data, K):
            if not data:
                return []
            if not K:
                return []

            pivot = data[random.randint(0, len(data)-1)][0]
            left, right = [], []

            for count, num in data:
                if count < pivot:
                    left.append((count, num))
                else:
                    right.append((count, num))
            
            if len(right) == K:
                return right
            if len(right) > K:
                return quickSelect(right, K)

            return right + quickSelect(left, K - len(right))

        return [n for count, n in quickSelect(nums_cnts, k)]

        # 09/08/24 meta phone screen prep
        # need to redo top k , read the editorial.
        
        # method 1: use counter
        # return [x[0] for x in Counter(nums).most_common(k)]
    
        # method 2: use quickselect
        
        # c = defaultdict(int)
        # for n in nums:
        #     c[n] += 1
            
        # def sort(arr, l, r, K):
        #     if l < r:
        #         p = partition(arr, l, r)
        #         if p == len(arr) - K:
        #             return
        #         elif p < len(arr) - K:
        #             sort(arr, p+1, r, K)
        #         else:
        #             sort(arr, l, p-1, K)
        # def partition(arr, l, r):
        #     pivot_ind = random.randint(l, r)
        #     arr[pivot_ind], arr[r] = arr[r], arr[pivot_ind]
        #     written = l-1
        #     for i in range(l, r):
        #         if c[arr[i]] < c[arr[r]]:
        #             written += 1
        #             arr[written], arr[i] = arr[i], arr[written]
        #     written += 1
        #     arr[written], arr[r] = arr[r], arr[written]
        #     return written
        
        # uniq = list(set(nums))
        # sort(uniq, 0, len(uniq)-1, k)
        # return uniq[len(uniq)-k:]
                
            
21600