#sol

1 messages · Page 1 of 1 (latest)

limpid zealot
# 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(n) time
        if len(nums) == k:
            return nums
        
        freq = Counter(nums)
        
        return [i for i,_ in freq.most_common(k)]
patent cliff
# 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        buckets = [[] for _ in range(len(nums) + 1)]
        counter = {}
        for x in nums:
            if x in counter:
                counter[x] += 1
            else: counter[x] = 1
        for x in counter:
            buckets[counter[x]].append(x)
        out = []
        for i in range(len(buckets) - 1, -1, -1):
            out.extend(buckets[i])
            if len(out) == k:
                return out
#

buckets are better cause O(N)

tribal tinsel
#

i'm pretty sure you can use bucket sort for O(n) worst ase

unknown.png
limpid zealot
#

honestly, that bucket thing is too much for me

#

its prolly better yes, but too much of a hassle

tribal tinsel
#

I'm surprised they didn't put it in

limpid zealot
#

I can explain my solution perfectly

#

even if its 4 lines

#

but it doesnt matter honestly as long as u get ur sol

boreal pulsar
#

I went with bucket sort on this one. Because Neetcode said so 😂

limpid zealot
#

actually, the quickselect is N^2 in worst case

#

and the heap is nlogn in worst case

patent cliff
#

nah you can get O(n) quickselect

limpid zealot
#

u can

#

but big O is worst case

patent cliff
#

deterministically you can use the rank k linear time algorithm

#

Theta(n)

tribal tinsel
#

wtf is that

limpid zealot
#

LMAOOO yeah not doing that in interview

#

u lost me right there

tribal tinsel
#

this looks like a college paper, I'm done with college

patent cliff
#

ya HAHA

boreal pulsar
#

O(n) for bucket sort seems good enough for me lololol

patent cliff
#

bucket sort is the best one for sure

#

trust me

#

but heap is next best

#

definitely passable

limpid zealot
#

ohh bucket sort is genius!!