Initial Solution
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
# find max
res = []
for _ in range(0, k):
max_cnt = -1
for cnt in count.values():
if cnt > max_cnt:
max_cnt = cnt
# res
found = False
for i, cnt in enumerate(count.values()):
if cnt == max_cnt:
for q, key in enumerate(count.keys()):
if i == q:
res.append(key)
count[key] = -10000
found = True
break
if found:
break
return res
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n * k) where n is the length of nums. For each of k iterations, we scan through the entire count dictionary to find the maximum, making it inefficient.
Space Complexity: O(n) for storing the count dictionary, where n is the number of unique elements in nums.
What I didn’t know
•
sorting map with certain criteria
◦
Method 1: Using sorted() with lambda
# Example: Sort dictionary by values in descending order
count = {3: 4, 1: 2, 2: 5, 5: 1}
# Sort by values (descending)
sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)
# Result: [(2, 5), (3, 4), (1, 2), (5, 1)]
# Get top k keys
k = 2
result = [key for key, value in sorted_items[:k]]
# Result: [2, 3]
Python
복사
◦
Method 2: Using Counter.most_common()
from collections import Counter
# Example: Find k most frequent elements
nums = [1, 1, 1, 2, 2, 3]
k = 2
count = Counter(nums)
# Counter({1: 3, 2: 2, 3: 1})
# Get k most common elements
result = [key for key, freq in count.most_common(k)]
# Result: [1, 2]
Python
복사
◦
Method 3: Using Bucket Sort (O(n) time)
# Example: Bucket sort approach for O(n) solution
nums = [1, 1, 1, 2, 2, 3]
k = 2
# Count frequencies
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
# Create buckets where index = frequency
freq = [[] for i in range(len(nums) + 1)]
for num, cnt in count.items():
freq[cnt].append(num)
# freq[1] = [3], freq[2] = [2], freq[3] = [1]
# Get k elements from highest frequency buckets
result = []
for i in range(len(freq) - 1, 0, -1):
for num in freq[i]:
result.append(num)
if len(result) == k:
break
if len(result) == k:
break
# Result: [1, 2]
Python
복사
•
how to find key with the val?
# Method 1: Using list comprehension with condition
count = {3: 4, 1: 2, 2: 5, 5: 1}
target_value = 5
# Find all keys with the target value
keys = [key for key, val in count.items() if val == target_value]
# Result: [2]
# Find first key with the target value
key = next((k for k, v in count.items() if v == target_value), None)
# Result: 2
Python
복사
# Method 2: Using a loop (more explicit)
for key, val in count.items():
if val == target_value:
print(f"Found key: {key}")
break
Python
복사
Other Better Solutions
1.
using sorted function for brief codes
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
# sorting counts array and return
sorted_arr = sorted(count.items(), key=lambda x: x[1], reverse= True)
res = [num for num, freq in sorted_arr[:k]]
return res
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n log n) where n is the number of unique elements. The sorting step dominates with O(n log n), and building the count dictionary takes O(n) time where n is the length of nums.
Space Complexity: O(n) for storing the count dictionary and the sorted array, where n is the number of unique elements in nums.
2.
Bucket Sort
class Solution(object):
def topKFrequent(self, nums, k):
from collections import defaultdict
freq = defaultdict(int)
for x in nums:
freq[x] += 1
# buckets[i] = list of numbers that appear exactly i times
n = len(nums)
buckets = [[] for _ in range(n + 1)]
for num, c in freq.items():
buckets[c].append(num)
res = []
for c in range(n, 0, -1):
if buckets[c]:
for num in buckets[c]:
res.append(num)
if len(res) == k:
return res
Python
복사
How Bucket Sort Works Here
The bucket sort approach is clever because it uses the frequency count as an index in an array:
a.
Create frequency map: First, count how many times each number appears in the input array.
b.
Create buckets: Make an array of empty lists where buckets[i] will store all numbers that appear exactly i times. The array size is n+1 where n is the length of the input, since a number can appear at most n times.
c.
Fill buckets: For each number and its frequency count, add that number to the bucket at index count. For example, if number 5 appears 3 times, add 5 to buckets[3].
d.
Collect results: Start from the highest frequency bucket (index n) and work backwards. Take numbers from each non-empty bucket and add them to the result until you have k numbers.
Example walkthrough:
Input: nums = [1,1,1,2,2,3], k = 2
a.
Frequency map: {1: 3, 2: 2, 3: 1}
b.
Buckets after filling:
buckets[0] = []
buckets[1] = [3] # 3 appears 1 time
buckets[2] = [2] # 2 appears 2 times
buckets[3] = [1] # 1 appears 3 times
buckets[4] = []
buckets[5] = []
buckets[6] = []
Python
복사
c.
Iterate from highest to lowest frequency:
•
Start at buckets[6] → empty, skip
•
Continue to buckets[3] → contains [1], add 1 to result → res = [1]
•
Continue to buckets[2] → contains [2], add 2 to result → res = [1, 2]
•
We have k=2 elements, return [1, 2]
Time complexity and Space Complexity
Time Complexity: O(n) where n is the length of nums. We iterate through nums once to build the frequency map O(n), create buckets O(n), and collect results from buckets O(n).
Space Complexity: O(n) for storing the frequency dictionary and the buckets array, where n is the length of nums.