Leetcode Practice
LC 347. Top K Frequent Elements
- Last updated
- Reading time
- 2 min read
The problem
Time
First Solution -For my solution, I count and store each number's frequency in a map. I then convert to a 2D array, sort in descending, and return the first k
numbers.
The time complexity is the result of sorting the 2D array by frequency.
function topKFrequent(nums: number[], k: number): number[] {
let map = {}
for (let i = 0; i < nums.length; i++) {
if (!map[nums[i]]) {
map[nums[i]] = 1
} else {
map[nums[i]] += 1
}
}
let arr: [string, number][] = Object.entries(map)
arr.sort((a, b) => b[1] - a[1])
return arr.filter((_, idx) => idx < k).map((x) => parseInt(x[0]))
}
More efficient solution
To make one modification over my original, I would ditch the filter
-map
combo to avoid an unnecessary iteration.
function topKFrequent(nums: number[], k: number): number[] {
let map = {}
for (let i = 0; i < nums.length; i++) {
if (!map[nums[i]]) {
map[nums[i]] = 1
} else {
map[nums[i]] += 1
}
}
let arr: [string, number][] = Object.entries(map)
arr.sort((a, b) => b[1] - a[1])
let res = []
for (let i = 0; i < k; i++) {
res.push(parseInt(arr[i][0]))
}
return res
}