Leetcode: 347. Top K Frequent Elements
Naive solution using dictionary
- Primary idea: Use dictionary to count frequency of all elements, sort the dictionary to find the top K frequent elements
- Time Complexity: O(logn)
- Space Complexity: O(n)
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var frequencyDict = [Int: Int]()
for num in nums {
frequencyDict[num, default: 0] += 1
}
let sortedDict = frequencyDict.sorted { $0.value > $1.value }
var result = [Int]()
for i in 0 ..< k {
result.append(sortedDict[i].key)
}
return result
}
print(topKFrequent([3, 1, 4, 4, 5, 2, 6, 1], 2)) // [1, 4]
print(topKFrequent([1, 1, 1, 2, 2, 3], 2)) // [1, 2]
print(topKFrequent([1], 1)) // 1Optimised solution using bucket sort
- Primary idea: Use dictionary to count frequency and use buckets sort to group the elements by their frequency in the buckets
- Time Complexity: O(n)
- Space Complexity: O(n)
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var freqMap = [Int: Int]()
// Create a frequency map freqMap by iterating through the array nums.
for num in nums {
freqMap[num, default: 0] += 1
}
// Group the elements by their frequency in the buckets.
// Each bucket at index i contains all the elements that have a frequency of i.
var buckets = Array(repeating: [Int](), count: nums.count + 1)
for (num, freq) in freqMap {
buckets[freq].append(num)
}
// Iterate through the buckets array in reverse order and add the elements to the result array until its size becomes equal to k
var result = [Int]()
for i in (0 ..< buckets.count).reversed() {
result += buckets[i]
if result.count == k {
break
}
}
return result
}
print(topKFrequent([3, 1, 4, 4, 5, 2, 6, 1], 2)) // [1, 4]
print(topKFrequent([1, 1, 1, 2, 2, 3], 2)) // [1, 2]
print(topKFrequent([1], 1)) // 1