Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

347. Top K Frequent Elements

Time: $O(n\log k)$

Space: $O(n)$

			


struct T {
  int num;
  int freq;
  T(int num, int freq) : num(num), freq(freq) {}
};

class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    const int n = nums.size();
    vector<int> ans;
    unordered_map<int, int> count;
    auto compare = [](const T& a, const T& b) { return a.freq > b.freq; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);

    for (const int num : nums)
      ++count[num];

    for (const auto& [num, freq] : count) {
      minHeap.emplace(num, freq);
      if (minHeap.size() > k)
        minHeap.pop();
    }

    while (!minHeap.empty())
      ans.push_back(minHeap.top().num), minHeap.pop();

    return ans;
  }
};




			


class T {
  public int num;
  public int freq;
  public T(int num, int freq) {
    this.num = num;
    this.freq = freq;
  }
}

class Solution {
  public int[] topKFrequent(int[] nums, int k) {
    final int n = nums.length;
    int[] ans = new int[k];
    Map<Integer, Integer> count = new HashMap<>();
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.freq - b.freq);

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      final int num = entry.getKey();
      final int freq = entry.getValue();
      minHeap.offer(new T(num, freq));
      if (minHeap.size() > k)
        minHeap.poll();
    }

    for (int i = 0; i < k; ++i)
      ans[i] = minHeap.poll().num;

    return ans;
  }
}