556. Trending Words
A social feed collects every word users typed in the last hour into the array words. To fill the "trending" panel you must return the k words that appear most often.
Sort the distinct words by how many times they occur, highest first. When two words occur equally often, the one that comes first in dictionary (lexicographic) order is listed first. Return the first k words of that ordering as an array of strings; if there are fewer than k distinct words, return all of them.
Words consist of lower-case English letters only. With d distinct words, aim for O(n + d + k log d) time (or O(n log k) using a bounded heap) and O(d) space, instead of repeatedly scanning all words.
Example 1
- Input:
- words = ["rain","sun","rain","wind","sun","rain"], k = 2
- Output:
- ["rain","sun"]
- Explanation:
"rain" occurs 3 times, "sun" 2 times and "wind" once, so the top two are "rain" then "sun".
Example 2
- Input:
- words = ["pear","fig","plum","fig","pear"], k = 2
- Output:
- ["fig","pear"]
- Explanation:
"fig" and "pear" both occur twice, and "fig" comes first alphabetically.
Example 3
- Input:
- words = ["b","a","c"], k = 3
- Output:
- ["a","b","c"]
- Explanation:
Every word occurs once, so the dictionary order a, b, c decides.
Constraints
- 1 ≤
words.length≤ 105 - 1 ≤
words[i].length≤ 10, lower-case English letters only - 1 ≤
k≤ 105 (ifkexceeds the number of distinct words, return all distinct words)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n + d + k log d)
- Space
- O(d)