Skip to main content

692. Top K Frequent Words

mediumAsked at Amazon

Given an array of strings and integer k, return the k most frequent words sorted by frequency (descending) then lexicographically (ascending). Amazon asks this to test whether you handle the dual-key sort cleanly in a heap or a comparator.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a top-K variant.
  • Blind (2025-11)— Recurring Amazon interview problem.

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"]

Example 2

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

Approaches

1. Hash + sort with custom comparator

Count occurrences. Sort by (-count, lexicographic). Take top k.

Time
O(n log n)
Space
O(n)
function topKFrequentSort(words, k) {
  const counts = new Map();
  for (const w of words) counts.set(w, (counts.get(w) || 0) + 1);
  return [...counts.entries()].sort((a, b) => {
    if (a[1] !== b[1]) return b[1] - a[1];
    return a[0].localeCompare(b[0]);
  }).slice(0, k).map(e => e[0]);
}

Tradeoff: Simple and clear. Often the right answer for this problem size.

2. Min-heap with custom comparator (optimal)

Push entries into a min-heap keyed by (count, REVERSED string). Pop when size > k. Result reversed.

Time
O(n log k)
Space
O(n + k)
// MinHeap with a custom compare function — entries are [count, word]
// where 'smaller' means: count is smaller, OR (count equal AND word is lexicographically LARGER).
class MinHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { if (!this.data.length) return; const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  size() { return this.data.length; }
  _less(a, b) {
    if (a[0] !== b[0]) return a[0] < b[0];
    return a[1] > b[1]; // for ties, larger word is 'less' so it pops first
  }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (!this._less(this.data[i], this.data[p])) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this._less(this.data[l], this.data[best])) best = l; if (r < this.data.length && this._less(this.data[r], this.data[best])) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

function topKFrequent(words, k) {
  const counts = new Map();
  for (const w of words) counts.set(w, (counts.get(w) || 0) + 1);
  const heap = new MinHeap();
  for (const [w, c] of counts) {
    heap.push([c, w]);
    if (heap.size() > k) heap.pop();
  }
  const out = [];
  while (heap.size()) out.push(heap.pop()[1]);
  return out.reverse();
}

Tradeoff: The tricky bit is the comparator: for ties, the LARGER word should pop first (because we want the smaller word to remain in the heap, which corresponds to it being in the top-K). Reverse the output at the end.

Amazon-specific tips

Amazon interviewers grade this on whether you handle the lexicographic tiebreaker. State out loud: 'When counts tie, smaller word ranks higher. So in a MIN-heap of top-K, on a count tie, the LARGER word is at the root so it pops first when size exceeds K.' Getting the comparator direction wrong is the #1 bug.

Common mistakes

  • Reversing the lexicographic tiebreaker direction (smaller word should be kept; larger should pop).
  • Forgetting to reverse the heap-drain at the end.
  • Using localeCompare without considering case sensitivity (problem says lowercase only).

Follow-up questions

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

  • What if there's a global ban list (skip certain words)?
  • What if you needed top-K trending words (with time decay)?
  • What if k were a fraction of unique words?

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 comparator direction confusing?

In a min-heap, smaller items are at the root and pop first. We want the WORSE word (lower-ranked) to pop first. Lower count = worse. Equal count + larger lexicographically = worse. So the comparator says 'larger word is less' for ties.

Sort or heap — which does Amazon prefer?

Both work. Sort is simpler. Heap shows you can manage the per-element pop. For an interview, lead with sort, then offer heap if asked to optimize.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →