Leetcode Practice

LC 347. Top K Frequent Elements

Last updated
Reading time
2 min read

The problem

First Solution - O(nlogn)O(n \log n) Time

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
}