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

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition - Max-Heap

The two main challenges to this problem are:

1. Identifying the k most frequent strings.
2. Sorting those strings first by frequency and then lexicographically.

For now, let's concentrate on identifying the most frequent strings and address lexicographical ordering afterward.

First, we need a way to keep track of the frequencies of each string. We can use a hash map for this, where the keys represent the strings and the values represent frequencies:

The most straightforward approach is to obtain an array containing the strings from the hash map, sorted by frequency in descending order. The k most frequent strings would be the first k strings in this array.

The main inefficiency of this solution is that it involves sorting all n strings, even though we only need the top k frequent ones to be sorted.

Something useful to consider: if we remove the most frequent string, the new most frequent string after this removal represents the second-most frequent overall. By repeatedly identifying and removing the most frequent string k times, we efficiently obtain our answer.

To implement this idea, we need a data structure that allows efficient access to the most frequent string at any time. A max-heap is perfect for this.

Max-heap
Let's find the k most frequent strings from the previous input, this time using a max-heap. First, populate the heap with each string along with their frequencies.

One way to populate the heap is to push all n strings into it one by one, which will take $O(n\log(n))$ time. Instead, we can perform the heapify operation on an array containing all the string-frequency pairs to create the max-heap in $O(n)$ time.

To collect the k most frequent strings, pop off the top element from the heap k times and store the corresponding strings in the output array res:

Now, we just need to ensure that when two strings have the same frequency, the one that comes first lexicographically has a higher priority in the heap. To do this, we can define a custom comparator for the heap that prioritizes strings lexicographically when their frequencies match, as demonstrated in the implementation below.

Implementation - Max-Heap

We create a Pair class for string-frequency pairs, enabling us to customize priority using a custom comparator.

from typing import List
from collections import Counter
import heapq
    
class Pair:
   def __init__(self, str, freq):
       self.str = str
       self.freq = freq
    
   # Define a custom comparator.
   def __lt__(self, other):
       # Prioritize lexicographical order for strings with equal frequencies.
       if self.freq == other.freq:
           return self.str < other.str
       # Otherwise, prioritize strings with higher frequencies.
       return self.freq > other.freq
    
def k_most_frequent_strings_max_heap(strs: List[str], k: int) -> List[str]:
   # We use 'Counter' to create a hash map that counts the frequency of each string.
   freqs = Counter(strs)
   # Create the max heap by performing heapify on all string-frequency pairs.
   max_heap = [Pair(str, freq) for str, freq in freqs.items()]
   heapq.heapify(max_heap)
   # Pop the most frequent string off the heap 'k' times and return these 'k' most
   # frequent strings.
   return [heapq.heappop(max_heap).str for _ in range(k)]

struct Pair { string s; int freq; };
struct MaxCmp {                                  // top() = highest freq; ties: lexicographically smaller
    bool operator()(const Pair& a, const Pair& b) const {
        if (a.freq != b.freq) {
            return a.freq < b.freq;              // lower freq = lower priority
        }
        return a.s > b.s;                        // tie: later letter = lower priority
    }
};
vector<string> kMostFrequentStringsMaxHeap(vector<string>& strs, int k) {
    unordered_map<string, int> freqs;
    for (auto& s : strs) {
        freqs[s]++;
    }
    vector<Pair> arr;
    for (auto& [s, f] : freqs) {
        arr.push_back({s, f});
    }
    priority_queue<Pair, vector<Pair>, MaxCmp> maxHeap(MaxCmp(), arr);   // O(n) heapify
    vector<string> res;
    for (int i = 0; i < k; i++) {
        res.push_back(maxHeap.top().s);
        maxHeap.pop();
    }
    return res;
}

static class Pair { String s; int freq; Pair(String s, int f){ this.s = s; this.freq = f; } }

List<String> kMostFrequentStringsMaxHeap(String[] strs, int k) {
    Map<String,Integer> freqs = new HashMap<>();
    for (String s : strs) freqs.merge(s, 1, Integer::sum);
    // poll() returns the most important: highest freq, ties alphabetical
    PriorityQueue<Pair> maxHeap = new PriorityQueue<>((a, b) ->
        a.freq != b.freq ? b.freq - a.freq : a.s.compareTo(b.s));
    for (Map.Entry<String,Integer> e : freqs.entrySet())
        maxHeap.offer(new Pair(e.getKey(), e.getValue()));
    List<String> res = new ArrayList<>();
    for (int i = 0; i < k; i++) res.add(maxHeap.poll().s);
    return res;
}

Complexity Analysis

Time complexity: The time complexity of k_most_frequent_strings_max_heap is $O(n+k\log(n))$.

• It takes $O(n)$ time to count the frequency of each string using Counter, and to build the max_heap.
• We also pop off the top of the heap $k$ times, with each pop operation taking $O(\log(n))$ time.

Therefore, the overall time complexity is $O(n)+kO(\log(n))=O(n+k\log(n))$.

Space complexity: The space complexity is $O(n)$ because the hash map and heap store at most $n$ pairs. Note that the output array is not considered in the space complexity.

Intuition - Min-Heap

As a follow up, your interviewer may ask you to modify your solution to reduce the space used by the heap.

In the previous approach, we ended up storing up to n items in the heap. However, since we only need the k most frequent characters, is there a way to maintain a heap with a space complexity of $O(k)$?

An important observation is that when our heap exceeds size k, we can discard the lowest frequency strings until the heap's size is reduced to k again. We can do this because those discarded strings definitely won't be among the k most frequent strings.

However, we can't implement this strategy with a max-heap because we won't have access to the lowest frequency string. Instead, we need to use a min-heap.

Let's observe how this works over an example:

In the end, the strings remaining in the heap are our top k frequent strings:

To retrieve these strings, pop them from the heap until it's empty. Because we're using a min-heap, we're popping off the less frequent strings first. So, we need to reverse the order of the retrieved strings before returning the result:

from typing import List
from collections import Counter
import heapq
    
class Pair:
    def __init__(self, str, freq):
        self.str = str
        self.freq = freq
    # Since this is a min-heap comparator, we can use the same comparator as the one
    # used in the max-heap, but reversing the inequality signs to invert the priority.
    def __lt__(self, other):
        if self.freq == other.freq:
            return self.str > other.str
        return self.freq < other.freq
    
def k_most_frequent_strings_min_heap(strs: List[str], k: int) -> List[str]:
    freqs = Counter(strs)
    min_heap = []
    for str, freq in freqs.items():
        heapq.heappush(min_heap, Pair(str, freq))
        # If heap size exceeds 'k', pop the lowest frequency string to ensure the heap
        # only contains the 'k' most frequent words so far.
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    # Return the 'k' most frequent strings by popping the remaining 'k' strings from
    # the heap. Since we're using a min-heap, we need to reverse the result after
    # popping the elements to ensure the most frequent strings are listed first.
    res = [heapq.heappop(min_heap).str for _ in range(k)]
    res.reverse()
    return res

struct MinCmp {                                  // top() = LEAST important (first to be dropped)
    bool operator()(const Pair& a, const Pair& b) const {
        if (a.freq != b.freq) {
            return a.freq > b.freq;
        }
        return a.s < b.s;
    }
};
vector<string> kMostFrequentStringsMinHeap(vector<string>& strs, int k) {
    unordered_map<string, int> freqs;
    for (auto& s : strs) {
        freqs[s]++;
    }
    priority_queue<Pair, vector<Pair>, MinCmp> minHeap;
    for (auto& [s, f] : freqs) {
        minHeap.push({s, f});
        if ((int)minHeap.size() > k) {
            minHeap.pop();                       // keep only the k most frequent
        }
    }
    vector<string> res;
    while (!minHeap.empty()) {
        res.push_back(minHeap.top().s);
        minHeap.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}

List<String> kMostFrequentStringsMinHeap(String[] strs, int k) {
    Map<String,Integer> freqs = new HashMap<>();
    for (String s : strs) freqs.merge(s, 1, Integer::sum);
    // poll() returns the LEAST important (the one to discard); ties -> later letter
    PriorityQueue<Pair> minHeap = new PriorityQueue<>((a, b) ->
        a.freq != b.freq ? a.freq - b.freq : b.s.compareTo(a.s));
    for (Map.Entry<String,Integer> e : freqs.entrySet()) {
        minHeap.offer(new Pair(e.getKey(), e.getValue()));
        if (minHeap.size() > k) minHeap.poll();
    }
    List<String> res = new ArrayList<>();
    while (!minHeap.isEmpty()) res.add(minHeap.poll().s);
    Collections.reverse(res);
    return res;
}

Complexity Analysis

Time complexity: The time complexity of k_most_frequent_strings_min_heap is $O(n\log(k))$.

• It takes $O(n)$ time to count the frequency of each string using Counter.
• To populate the heap, we push $n$ words onto it, with each push and pop operation taking $O(\log(k))$ time. This takes $O(n\log(k))$ time.
• Then, we extract $k$ strings from the heap by performing the pop operation $k$ times. This takes $O(k\log(k))$ time.
• Finally, we reverse the output array, which takes $O(k)$ time.

Therefore, the overall time complexity is $O(n)+O(n\log(k))+O(k\log(k))+O(k)=O(n\log(k))$.

Space complexity: The space complexity is $O(n)$ because the hash map stores at most $n$ pairs, whereas the heap only takes up $O(k)$ space. The res array is not considered in the space complexity.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language