#122

K Most Frequent Strings

medium

heap-priority-queuehash-tablesortingstring

Given an array of strings strs and an integer k, return the k most frequent strings.

Return the answer sorted by frequency from highest to lowest. When two strings have the same frequency, order them lexicographically (alphabetical, ascending) — so the result is fully deterministic.

For example, with strs = ["go", "coding", "byte", "byte", "go", "interview", "go"] and k = 2, the counts are go: 3, byte: 2, and coding/interview once each. The two most frequent are ["go", "byte"].

Example

Input: strs = ["go","coding","byte","byte","go","interview","go"], k = 2

Output: ["go","byte"]

go appears 3 times, byte twice; both beat the single-count strings.

Constraints

1 <= strs.length <= 10^4
1 <= strs[i].length <= 20
strs[i] consists of lowercase English letters.
1 <= k <= the number of distinct strings in strs.

Intuition

The direct approach counts every string, turns the counts into a list, fully sorts that list by the required order (frequency descending, then lexicographic ascending), and takes the first k.

function kMostFrequent(strs, k) {
  // Tally each string's frequency.
  const count = new Map();
  for (const s of strs) count.set(s, (count.get(s) || 0) + 1);
  // Sort every distinct string by frequency desc, breaking ties lexicographically asc.
  const distinct = [...count.keys()];
  distinct.sort((a, b) =>
    count.get(b) - count.get(a) || (a < b ? -1 : 1)
  );
  return distinct.slice(0, k);            // the top k after a full sort
}

Brute force — count, then sort all d distinct strings: O(n + d log d).

Counting is O(n), but the full sort costs O(d log d) over all d distinct strings — and we only want the top k. When k ≪ d, sorting everything is wasted work. Can we do better?

The key observation: to keep the k most frequent, hold a min-heap of size `k` ordered by how weak a candidate is — lowest frequency at the top, and on a frequency tie the lexicographically larger string on top (because we want to keep the smaller one). Push each distinct string; whenever the heap exceeds k, pop the weakest. Anything weaker than the current root never displaces it, so each push is O(log k). This is the bounded top-k heap from the Heaps intro.

The heap drains weakest-first, so reverse the drained order to present strongest-first.

Walking it through strs = [go, coding, byte, byte, go, interview, go], k = 2 (counts: go=3, byte=2, coding=1, interview=1):

size-2 min-heap keyed by weakness (top = weakest: lowest freq, then larger string)

push↓

go·3

coding·1

byte·2

interview·1

push go·3 → heap {go·3}

First distinct string enters. Heap under size k = 2, no eviction.

go·3

push↓

coding·1

byte·2

interview·1

push coding·1 → {coding·1, go·3}, size 2 — ok

coding (count 1) joins. Heap is exactly size 2; weakest (coding·1) is at the top.

go·3

coding·1

push↓

byte·2

interview·1

push byte·2 → size 3 > 2 → pop coding·1

byte (count 2) enters and overflows the heap; evict the weakest, coding·1. Heap {byte·2, go·3}.

go·3

coding·1

byte·2

push↓

interview·1

push interview·1 → size 3 > 2 → pop interview·1

interview (count 1) is weaker than the root byte·2, so it's pushed and immediately evicted.

go·3

coding·1

byte·2

interview·1

drain {byte·2, go·3} weakest-first → [byte, go], reverse → [go, byte]

Two strings remain. Draining gives byte then go; reverse for strongest-first. Answer: [go, byte].

Optimization

Count, then size-k min-heap

Count every string in a hash map (O(n)). Then keep a min-heap of the best k candidates seen so far, ordered so the weakest candidate sits on top — weakest meaning lowest frequency, and among equal frequencies the lexicographically larger string (because on a tie we prefer the smaller string, so the larger one is the first to be evicted). Push each distinct string; whenever the heap exceeds k, pop the weakest. After all distinct strings are processed the heap holds exactly the k answers.

Draining a min-heap yields weakest-first, so reverse it to get highest-frequency first (with lexicographic ascending order within a tie).

Counting is O(n); each of the d distinct strings does an O(log k) heap op, so O(n + d log k) time and O(d) space.

function kMostFrequent(strs, k) {
  // Frequency of every string.
  const count = new Map();
  for (const s of strs) count.set(s, (count.get(s) || 0) + 1);

  // A candidate a is "weaker" than b if it should be evicted first: lower frequency,
  // or — on equal frequency — the lexicographically larger string (we keep the smaller).
  const weaker = (a, b) => {
    if (count.get(a) !== count.get(b)) return count.get(a) < count.get(b);
    return a > b;
  };

  // Min-heap keyed by "weaker": heap[0] is the weakest candidate, the eviction target.
  const heap = [];
  const swap = (i, j) => { const t = heap[i]; heap[i] = heap[j]; heap[j] = t; };
  const up = (i) => {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!weaker(heap[i], heap[parent])) break;
      swap(parent, i);
      i = parent;
    }
  };
  const down = (i) => {
    const n = heap.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && weaker(heap[l], heap[smallest])) smallest = l;
      if (r < n && weaker(heap[r], heap[smallest])) smallest = r;
      if (smallest === i) break;
      swap(i, smallest);
      i = smallest;
    }
  };
  const push = (x) => { heap.push(x); up(heap.length - 1); };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) { heap[0] = last; down(0); }
    return top;
  };

  // Keep only the k strongest by evicting the weakest whenever the heap overflows.
  for (const s of count.keys()) {
    push(s);
    if (heap.length > k) pop();
  }

  // The heap drains weakest-first; reverse so the strongest (highest frequency) comes first.
  const result = [];
  while (heap.length > 0) result.push(pop());
  result.reverse();
  return result;
}

Complexity analysis

Time complexity: O(n + d log k) for n strings and d distinct values. Here's why:

Counting every string into the map is O(n).
Each of the d distinct strings does one O(log k) push (and possibly one O(log k) pop) on a heap bounded at size k.

So the heap phase is O(d log k), giving O(n + d log k) overall — cheaper than the O(n + d log d) full sort when k ≪ d.

Space complexity: O(d). Here's why:

The frequency map holds one entry per distinct string — O(d).
The heap holds at most k strings — O(k), and k ≤ d.

So the map dominates at O(d) (not counting the output array of k strings).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
strs = ["a"], k = 1	["a"]	Single string, k = 1 — the only answer.
strs = ["a","b"], k = 2	["a","b"]	k equals the distinct count: every string qualifies, ordered lexicographically on the all-1 tie.
strs = ["c","a","b"], k = 2	["a","b"]	All count 1 — the tie-break keeps the two lexicographically smallest.
strs = ["p","p","q","q","r"], k = 2	["p","q"]	p and q tie at count 2; both beat r (count 1), ordered p < q.
strs = ["go","go","go","byte","byte","run"], k = 2	["go","byte"]	Distinct frequencies (3, 2, 1) — top two by frequency, no tie.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor