Most Common Tags
MediumHeap / Priority Queue
Problem
A Q&A site labels each post with one technology tag; tags lists the tag of every post. Return the k most used tags, from most to least used.
When two tags are used the same number of times, the one that comes first alphabetically ranks higher.
Example 1
- Input:
- tags = ["go", "rust", "go", "java", "rust", "go"], k = 2
- Output:
- ["go", "rust"]
go appears 3 times, rust 2 times, java once.
Example 2
- Input:
- tags = ["b", "a", "c"], k = 2
- Output:
- ["a", "b"]
All three tie at 1, so alphabetical order decides.
Constraints
- 1 ≤ tags.length ≤ 10^5
- 1 ≤ tags[i].length ≤ 15, lowercase letters only
- 1 ≤ k ≤ number of distinct tags
Hint
Show the first hint
First reduce the posts to a count per distinct tag.
Walkthrough
How to approach it
01Clarify before coding
- How are ties ordered? Alphabetically ascending: with equal counts, "dart" ranks above "kotlin".
- Is k guaranteed not to exceed the number of distinct tags? Yes.
- Should the output be sorted? Yes, best first, so the order is part of the answer.
02Brute force
Count tags with a hash map, sort all distinct tags by (-count, tag) and take the first k.
Cost: O(n + d log d) for d distinct tags. That is actually acceptable here; the heap version improves it to O(n + d log k), which matters when d is large and k small.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.