Back to Arrays
Q97Question 97 of 109

Find the Top K Frequent Elements

Key Concepts
  • Phase 1: count occurrences in a HashMap with a single linear pass using merge().
  • Phase 2: select the top k using a size-k min-heap keyed by frequency, evicting the least frequent when the heap exceeds k.
  • Counting is O(n); heap selection over m distinct values is O(m log k); total is O(n + m log k).
  • Bucket sort by frequency achieves O(n) total because counts are bounded by n.
  • The heap approach is preferred when k is small; bucket sort is preferred when k is large or latency matters.
  • Both approaches share the identical frequency-map phase and differ only in the selection step.

Definition

Count with a hash map, then keep the k highest counts in a size-k min-heap keyed by frequency.
  • Frequency counting – a single linear pass with map.merge(element, 1, Integer::sum) builds a count for each distinct element.
  • Min-heap selection – a PriorityQueue of size k ordered by frequency keeps the k most frequent; the root (least frequent of the leaders) is evicted when a higher count arrives.
  • Bucket sort alternative – create n+1 buckets indexed by frequency, drop each element into its count bucket, scan from highest bucket down to collect k elements in O(n).
  • Complexity – O(n + m log k) with heap, O(n) with bucket sort, where m is the count of distinct elements.

The National Bank of India wants the three most common merchant categories customers spend on. A clerk first tallies every transaction, one count per category. Then she keeps a small tray of three categories with the biggest counts, arranged so the smallest count is at the front for easy swap-out. For each new count, if it beats the front of the tray, she swaps it in. The tray holds the top three at the end.

Understanding the Concepts

What is the Top K Frequent Elements problem?

Given an array of elements, return the k elements that appear most frequently. For example, in [1,1,1,2,2,3] with k=2, the answer is [1, 2].

At the National Bank of India, the operations dashboard displays the k most frequent transaction types each day.

How does the frequency counting phase work?

A single pass builds a HashMap from element to its count.

JAVA
package com.bank.analytics;

import java.util.HashMap;
import java.util.Map;

public class FrequencyMap {
    public static Map<String, Integer> countFrequencies(String[] transactions) {
        Map<String, Integer> freq = new HashMap<>();
        for (String txn : transactions) {
            freq.merge(txn, 1, Integer::sum);
        }
        return freq;
    }

    public static void main(String[] args) {
        String[] txns = {"UPI", "NEFT", "UPI", "IMPS", "UPI", "NEFT"};
        System.out.println(countFrequencies(txns));
    }
}
TEXT
{UPI=3, NEFT=2, IMPS=1}

How does the min-heap selection work?

Maintain a min-heap of size k ordered by frequency. Offer each distinct element; if the heap exceeds k, poll the least frequent.

JAVA
package com.bank.analytics;

import java.util.*;

public class TopKFrequent {
    public static List<String> topKFrequent(String[] transactions, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String txn : transactions) {
            freq.merge(txn, 1, Integer::sum);
        }

        PriorityQueue<Map.Entry<String, Integer>> heap =
                new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        for (Map.Entry<String, Integer> entry : freq.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        List<String> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll().getKey());
        }
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        String[] txns = {"UPI", "NEFT", "UPI", "IMPS", "UPI", "NEFT", "RTGS"};
        System.out.println("Top 2: " + topKFrequent(txns, 2));
    }
}
TEXT
Top 2: [UPI, NEFT]

How does the bucket sort alternative work?

Since any count is between 1 and n, create n+1 buckets indexed by frequency. Drop each element into the bucket matching its count. Scan from the highest bucket down, collecting k elements.

JAVA
package com.bank.analytics;

import java.util.*;

public class TopKBucketSort {
    @SuppressWarnings("unchecked")
    public static List<String> topKFrequent(String[] transactions, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String txn : transactions) {
            freq.merge(txn, 1, Integer::sum);
        }

        List<String>[] buckets = new List[transactions.length + 1];
        for (Map.Entry<String, Integer> entry : freq.entrySet()) {
            int count = entry.getValue();
            if (buckets[count] == null) {
                buckets[count] = new ArrayList<>();
            }
            buckets[count].add(entry.getKey());
        }

        List<String> result = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
            if (buckets[i] != null) {
                result.addAll(buckets[i]);
            }
        }
        return result.subList(0, k);
    }

    public static void main(String[] args) {
        String[] txns = {"UPI", "NEFT", "UPI", "IMPS", "UPI", "NEFT", "RTGS"};
        System.out.println("Top 2 (bucket): " + topKFrequent(txns, 2));
    }
}
TEXT
Top 2 (bucket): [UPI, NEFT]

What is the time and space complexity?

| Approach | Counting | Selection | Total |
|---|---|---|---|
| Min-heap | O(n) | O(m log k) | O(n + m log k) |
| Bucket sort | O(n) | O(n) | O(n) |
| Full sort | O(n) | O(m log m) | O(n + m log m) |

The bucket sort approach is linear because it exploits the fact that frequencies are bounded by n.

How does the heap comparison work?

The heap is a min-heap by frequency, so the root always holds the least frequent of the current leaders. When a new entry arrives with a higher frequency than the root, the root is evicted and replaced.

JAVA
// Min-heap: smallest frequency at root
PriorityQueue<Map.Entry<String, Integer>> heap =
    new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

// After processing: heap contains exactly k entries
// Root = least frequent of the top k

What are common mistakes?

Using a max-heap instead of a min-heap. A max-heap would keep evicting the most frequent element, which is the opposite of what you want.

JAVA
// Wrong: max-heap evicts the most frequent
new PriorityQueue<>(Comparator.comparingInt(e -> -e.getValue()));

// Correct: min-heap evicts the least frequent
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

What are the edge cases?

  • k equals the number of distinct elements: return all distinct elements.
  • All elements identical: the single element is the only answer for k=1.
  • Multiple elements share the same frequency as the kth: the problem says "any order," so ties can be broken arbitrarily.

What should a senior engineer know?

The insight interviewers reward is recognizing that frequencies are bounded by n, which is exactly what makes bucket sort linear. Both approaches share the identical frequency-map phase; they differ only in selection.

For streaming data where you cannot wait for the full array, use the heap approach because it processes elements one at a time. For batch computation where latency matters, use bucket sort.

What are common interview follow-up questions?

  • What if k is very large, close to the number of distinct elements? (Bucket sort is better.)
  • What if elements arrive in a stream? (Use heap with the frequency map updated on each arrival.)
  • How would you handle ties? (Problem usually says any order; if not, add a secondary sort key.)

Visual Overview

TEXT
Transactions: [UPI, NEFT, UPI, IMPS, UPI, NEFT, RTGS]   k = 2

Phase 1 - Frequency Map:
  UPI  -> 3
  NEFT -> 2
  IMPS -> 1
  RTGS -> 1

Phase 2a - Min-Heap (size k=2):
  offer UPI(3)  -> heap: [UPI(3)]
  offer NEFT(2) -> heap: [NEFT(2), UPI(3)]
  offer IMPS(1) -> heap size 3 > k=2, poll IMPS(1) -> heap: [NEFT(2), UPI(3)]
  offer RTGS(1) -> heap size 3 > k=2, poll RTGS(1) -> heap: [NEFT(2), UPI(3)]
  Result: [UPI, NEFT]

Phase 2b - Bucket Sort:
  bucket[3] = [UPI]
  bucket[2] = [NEFT]
  bucket[1] = [IMPS, RTGS]
  Scan from top: bucket[3] -> UPI, bucket[2] -> NEFT. Collected 2. Done.
  Result: [UPI, NEFT]
DIAGRAM
┌──────────────────────────────────────────────────┐
│        Top K Frequent Elements Flow               │
├──────────────────────────────────────────────────┤
│                                                  │
│   Phase 1: Count frequencies                     │
│   ┌──────────────────────────────┐               │
│   │ for each element:            │               │
│   │   freq.merge(e, 1, sum)      │               │
│   └──────────────────────────────┘               │
│                │                                 │
│                ▼                                 │
│   Phase 2: Select top k                          │
│                                                  │
│   Option A: Min-Heap          Option B: Buckets  │
│   ┌──────────────────┐   ┌──────────────────┐    │
│   │ offer each entry │   │ bucket[count]=e  │    │
│   │ if size > k:     │   │ scan high to low │    │
│   │   poll smallest  │   │ collect k items  │    │
│   └──────────────────┘   └──────────────────┘    │
│                                                  │
│   Return top k elements                          │
└──────────────────────────────────────────────────┘

Key Takeaway

Finding the top k frequent elements splits into two phases. First, count occurrences in a single linear pass using a HashMap. Second, select the k highest counts from that map.

The min-heap approach keeps a heap of size k ordered by frequency. You offer each distinct element, and when the heap exceeds k, you poll the least frequent. After processing all entries, the heap holds the top k. This runs in O(n + m log k).

The bucket sort alternative exploits the fact that counts are bounded by n. Create n+1 buckets indexed by frequency, drop each element into its count bucket, and scan from the highest bucket down collecting k elements. That is O(n) with no log factor.

At the National Bank of India, the operations dashboard displayed the k most frequent transaction types for the day. Because daily volume was large and the dashboard had to refresh quickly, Rajesh used bucket sort for linear selection, keeping the min-heap as the fallback for streaming scenarios.

Remember one sentence: count with a HashMap, then select the top k with a size-k min-heap or bucket sort by frequency.

---

Share
Use ← → arrow keys to navigate