Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Top K Frequent Elements

Medium · Heap & Priority Queue · Asked at Amazon, Meta, Google, Microsoft, Yelp

Print the k most frequent values. Order them by frequency (highest first); if two values have the same frequency, the smaller value comes first.

Input

First line: n k. Second line: n integers.

Output

The k values, space-separated.

Constraints

Count with a hash map, then use a heap of size k (or bucket sort by frequency).

Example 1

Input

6 2
1 1 1 2 2 3

Output

1 2

Example 2

Input

1 1
1

Output

1

Hints

  1. Count every value with a hash map.
  2. Pick the k best (frequency desc, value asc) with a heap of size k, then output them in that order.

Approach

Build the frequency map. Keep a heap of size k whose top is the worst of the kept entries under the order "higher frequency, then smaller value"; push each (value, count) and pop when the size passes k. Finally sort the k kept entries best-first. Bucket sort by frequency gives O(n) too.

Complexity: O(n + d log k) time · O(d) space (d = distinct values)

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    // "better" = higher count, then smaller value; keep the k best, worst on top
    auto better = [](const pair<int, int> &a, const pair<int, int> &b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(better)> pq(better);
    for (auto &e : cnt) {
        pq.push(e);
        if ((int)pq.size() > k) pq.pop();
    }
    vector<pair<int, int>> v;
    while (!pq.empty()) v.push_back(pq.top()), pq.pop();
    sort(v.begin(), v.end(), better);
    for (size_t i = 0; i < v.size(); i++) cout << v[i].first << (i + 1 < v.size() ? " " : "\n");
    return 0;
}

Python solution

import sys
import heapq
from collections import Counter

data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
cnt = Counter(data[2 : 2 + n])
best = heapq.nsmallest(k, cnt.items(), key=lambda e: (-e[1], e[0]))
print(*[v for v, _ in best])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) cnt.merge(sc.nextInt(), 1, Integer::sum);
        Comparator<int[]> better = (a, b) -> a[1] != b[1] ? b[1] - a[1] : a[0] - b[0];
        PriorityQueue<int[]> pq = new PriorityQueue<>(better.reversed());
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            pq.add(new int[] {e.getKey(), e.getValue()});
            if (pq.size() > k) pq.poll();
        }
        List<int[]> v = new ArrayList<>(pq);
        v.sort(better);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < v.size(); i++) sb.append(v.get(i)[0]).append(i + 1 < v.size() ? " " : "");
        System.out.println(sb);
    }
}

Solve Top K Frequent Elements online · All practice problems