CODEWITHSUNDEEP
pythontime-complexitybig-o
dSisk
dSisk

Reputation: 25

LeetCode 347 Solution Time Complexity Calculation

I have been following Neetcode and working on several Leetcode problems. Here on 347 he advises that his solution is O(n), but I am having a hard time really breaking out the solution to determine why that is. I feel like it is because the nested for loop only runs until len(answers) == k.

I started off by getting the time complexity of each individual line and the first several are O(n) or O(1), which makes sense. Once I got to the nested for loop I was thrown off because it would make sense that the inner loop would run for each outer loop iteration and result in O(n*m), or something of that nature. This is where I think the limiting factor of the return condition comes in to act as the ceiling for the loop iterations since we will always return once the answers array length equals k (also, in the problem we are guaranteed a unique answer). What is throwing me off the most is that I default to thinking that any nested for loop is going to be O(n^2), which doesn't seem to be uncommon, but seems to not be the case every time.

Could someone please advise if I am on the right track with my suggestion? How would you break this down?

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        countDict = {}
        
        frequency = [[] for i in range(len(nums)+1)]
        
        for j in nums:
            countDict[j] = 1 + countDict.get(j, 0)  
            
        for c, v in countDict.items():
            frequency[v].append(c)
            
        answer = []
        
        for n in range(len(frequency)-1, 0, -1):
            for q in frequency[n]:
                print(frequency[n])
                answer.append(q)
                if len(answer) == k:
                    return answer

Upvotes: 0

Views: 172

Answers (1)

flakes
flakes

Reputation: 23644

frequency is mapping between frequency-of-elements and the values in the original list. The number of total elements inside of frequency is always equal or less than the number of original items in in nums (because it is mapping to the unique values in nums).

Even though there is a nested loop, it is still only ever iterating at some O(C*n) total values, where C <= 1 which is equal to O(n).

Note, you could clean up this answer fairly easily with some basic helpers. Counter can get you the original mapping for countDict. You can use a defaultdict to construct frequency. Then you can flatten the frequency dict values and slice the final result.

from collections import Counter, defaultdict


class Solution:
    def top_k_frequent(self, nums: list[int], k: int) -> list[int]:
        counter = Counter(nums)
        frequency = defaultdict(list)
        for num, freq in counter.items():
            frequency[freq].append(num)

        sorted_nums = []
        for freq in sorted(frequency, reverse=True):
            sorted_nums += frequency[freq]

        return sorted_nums[:k]

A fun way to do this in a one liner!

class Solution:
    def top_k_frequent(self, nums: list[int], k: int) -> list[int]:
        return sorted(set(nums), key=Counter(nums).get, reverse=True)[:k]

Upvotes: 1

Related Questions