All problems

Top K Streaming Words

Medium · heap

Words arrive one at a time. After each word arrives, you must report the k words seen most often so far, counting every word that has arrived up to and including this one.

A report lists words from the most frequent to the least frequent. If two words have been seen the same number of times, the one that comes first in alphabetical order goes first. If fewer than k different words have been seen, the report lists all of them.

Given the list words in arrival order and the number k, return a list of reports: entry i is the report made right after words[i] arrived.

Examples

Example 1

Input: words = ["pear", "fig", "pear", "kiwi", "fig", "fig"], k = 2

Output: [["pear"], ["fig", "pear"], ["pear", "fig"], ["pear", "fig"], ["fig", "pear"], ["fig", "pear"]]

After the third word pear has two sightings and fig one. After the fifth word fig and pear both have two, so alphabetical order puts fig first, and after the sixth fig leads with three. Kiwi, with one sighting, never makes the top two.

Example 2

Input: words = ["b", "a", "c", "a"], k = 3

Output: [["b"], ["a", "b"], ["a", "b", "c"], ["a", "b", "c"]]

With every word seen once, the reports are alphabetical. The last a gives it two sightings, ahead of the rest.

Example 3

Input: words = ["x", "x", "x"], k = 1

Output: [["x"], ["x"], ["x"]]

One word, reported every time.

Constraints