Town Baby Name Chart

MediumheapAlso known as Top K Frequent Words

Every January, a small town's newsletter prints a chart of the most popular baby names from last year. The registry office sends one long list with a name for every baby born, stored in lowercase, like ["mia", "leo", "mia", "ava"].

The chart shows the top k names, most popular first. When two names were given equally often, the editor lists them alphabetically, so nobody can claim the newsletter played favourites.

Your task

Write topNames(names, k). Return the k most frequent names, ordered by how many times they appear (highest first). Names with the same count go in alphabetical order.

Each name appears in the result at most once. k is never more than the number of different names.

topNames(names: string[], k: int) → string[]

Examples

Example 1

Input

names = ["mia", "leo", "mia", "ava", "leo", "mia", "zoe"]
k = 2

Output

["mia", "leo"]

Why

mia appears 3 times, leo 2, ava and zoe once each. The top 2 are mia, then leo.

Example 2

Input

names = ["noah", "eli", "ivy", "eli", "noah", "ivy", "amir"]
k = 3

Output

["eli", "ivy", "noah"]

Why

noah, eli and ivy all appear twice, so they tie and are listed alphabetically: eli, ivy, noah. Listing them in the order they first appear (noah, eli, ivy) would be wrong.

Constraints

1 ≤ names.length ≤ 20,000
1 ≤ k ≤ number of distinct names
Names use only lowercase letters a to z, 1 to 15 letters long.

Start with brute force

For each distinct name, count it by scanning the whole list again, then sort. Counting that way is O(n · m) for n babies and m distinct names, up to 400 million steps for 20,000 babies with all-different names.

Counting with a hash map fixes that. After counting, sorting all m names by (count, then name) costs O(m log m), which is fine here. A heap of size k cuts it to O(m log k), which helps when the list of distinct names is huge and the chart is short.

Hints

0 of 4 shown

Hint 1
Before ranking anything, what do you need to know about each name? How would you get that in a single pass over the list?
Hint 2
Count each name in a hash map. Now you have one entry per distinct name, and the job is to pick the best k of them. What exactly does "better" mean when two counts are equal?
Hint 3
Write one comparison rule: name A ranks above name B if A has a higher count, or the same count and A comes first alphabetically. Sorting every distinct name by that rule already works. Can you avoid sorting names that will never make the chart?
Hint 4
Keep a heap of at most k names with the weakest one on top (lowest count; for equal counts, the alphabetically later name). Push each distinct name, and pop when the heap grows past k. At the end, pop everything out (weakest first) and reverse it.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Two steps: count, then rank. The counting is a hash map. The ranking needs one clear rule, "higher count wins; on a tie, the alphabetically earlier name wins", and a way to keep only the best k without sorting everyone.

Trace the second example with k = 3. Counts: noah 2, eli 2, ivy 2, amir 1. The heap keeps the weakest name on top.

Push noah. Heap top: noah.
Push eli. Same count, but noah is later alphabetically, so noah is weaker and stays on top.
Push ivy. noah is still the weakest. Size 3.
Push amir (count 1). Size 4, so pop the weakest: amir, the only name with count 1.
Pop everything: noah, ivy, eli (weakest first). Reverse: ["eli", "ivy", "noah"].

The tie rule flips inside the heap: to keep the best names you evict the worst, and among equal counts the worst is the alphabetically later one. Getting that direction backwards is the usual bug. Python's heapq.nsmallest with the key (-count, name) runs this same size-k heap for you.

Reference solution

function topNames(names, k) {
  const count = new Map();
  for (const n of names) count.set(n, (count.get(n) || 0) + 1);
  // weaker(a, b): a ranks below b on the chart
  const weaker = (a, b) => count.get(a) < count.get(b) ||
    (count.get(a) === count.get(b) && a > b);
  const heap = []; // weakest kept name on top
  const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
  const push = (name) => {
    heap.push(name);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!weaker(heap[i], heap[parent])) break;
      swap(i, parent);
      i = parent;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length === 0) return top;
    heap[0] = last;
    let i = 0;
    while (true) {
      const l = 2 * i + 1, r = l + 1;
      let m = i;
      if (l < heap.length && weaker(heap[l], heap[m])) m = l;
      if (r < heap.length && weaker(heap[r], heap[m])) m = r;
      if (m === i) break;
      swap(i, m);
      i = m;
    }
    return top;
  };
 
  for (const name of count.keys()) {
    push(name);
    if (heap.length > k) pop(); // drop the weakest
  }
  const result = [];
  while (heap.length) result.push(pop()); // weakest first
  return result.reverse();
}

import heapq
from collections import Counter
 
def top_names(names, k):
    count = Counter(names)
    # Rank key: higher count first, then alphabetical.
    # nsmallest keeps a heap of size k internally: O(m log k).
    return heapq.nsmallest(k, count, key=lambda n: (-count[n], n))

TimeO(n + m log k)Counting is one pass over n names; each of the m distinct names costs O(log k) in the heap.

SpaceO(m)The count map holds every distinct name; the heap holds k.

Learn the idea: Heaps and Priority Queues Hash Tables

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code