Skip to main content

692. Top K Frequent Words

mediumAsked at DoorDash

Given an array of words and k, return the k most frequent strings sorted by frequency descending, then lexicographically ascending on ties. DoorDash uses this as the Top K Frequent Elements follow-up with the tie-breaker twist that catches careless candidates.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list Top K Frequent Words as the typical follow-up to LC 347.
  • Blind (2025-11)— DoorDash new-grad reports note the tie-breaker rule as the actual interview signal.

Problem

Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Constraints

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • k is in the range [1, The number of unique words[i]].

Examples

Example 1

Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i","love"]

Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Example 2

Input
words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output
["the","is","sunny","day"]

Approaches

1. Sort by composite key (clear)

Count frequencies. Take unique words; sort by (-freq, word). Return first k.

Time
O(n log n)
Space
O(n)
function topKFrequent(words, k) {
  const count = new Map();
  for (const w of words) count.set(w, (count.get(w) || 0) + 1);
  const unique = [...count.keys()];
  unique.sort((a, b) => {
    const fa = count.get(a), fb = count.get(b);
    if (fa !== fb) return fb - fa;
    return a < b ? -1 : a > b ? 1 : 0;
  });
  return unique.slice(0, k);
}

Tradeoff: Clearest expression. Composite sort key handles the tie-breaker explicitly. Bloomberg interviewers grade for this clarity.

2. Min-heap of size k with custom comparator

Maintain a min-heap by (freq, word). When the heap exceeds k, evict the smallest. Words with equal freq use REVERSED lex (since the heap is min over freq).

Time
O(n log k)
Space
O(n + k)
function topKFrequentHeap(words, k) {
  const count = new Map();
  for (const w of words) count.set(w, (count.get(w) || 0) + 1);
  const heap = [];
  function cmp(a, b) {
    if (a[0] !== b[0]) return a[0] - b[0];
    return b[1] < a[1] ? -1 : b[1] > a[1] ? 1 : 0;
  }
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (cmp(heap[p], heap[i]) > 0) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2;
        let small = i;
        if (l < heap.length && cmp(heap[l], heap[small]) < 0) small = l;
        if (r < heap.length && cmp(heap[r], heap[small]) < 0) small = r;
        if (small === i) break;
        [heap[i], heap[small]] = [heap[small], heap[i]];
        i = small;
      }
    }
    return top;
  }
  for (const [word, freq] of count) {
    push([freq, word]);
    if (heap.length > k) pop();
  }
  const result = [];
  while (heap.length) result.push(pop()[1]);
  return result.reverse();
}

Tradeoff: Faster when k << n. Tricky because the lex tie-break must be REVERSED in the comparator. Easy to get wrong under stress — start with the sort version unless the interviewer asks for O(n log k).

DoorDash-specific tips

DoorDash interviewers grade specifically on the TIE-BREAKER. State 'same frequency, smaller word first' BEFORE coding so the comparator is clear. The composite sort version is safer under pressure; reach for heap only if asked for the optimization.

Common mistakes

  • Forgetting the lex tie-break entirely.
  • Using lex ascending in the heap comparator (must be REVERSED relative to the freq comparator since the heap is min-over-freq).
  • Sorting the whole input array instead of the unique words.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Top K Frequent Elements (LC 347) — without the lex tie-break.
  • K Closest Points to Origin (LC 973) — heap with numeric tie-break.
  • Sort Characters By Frequency (LC 451) — full sort, no top-k.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the heap comparator tricky?

Because the heap is min-over-freq, ties on freq need the LEXICOGRAPHICALLY LARGER word to be 'smaller' in the heap so it gets evicted first. Easy to flip and ship a bug.

Sort or heap?

Sort if k is close to n. Heap if k is small. For interview clarity, start with sort and mention heap as an optimization.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Top K Frequent Words and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →