Top K Elements Explained

Quick answer

A top K elements problem asks for the k largest, smallest, most frequent, or highest-priority items from a larger collection.

The simplest solution is sorting, which is often O(n log n). A heap-based solution can reduce the work to O(n log k) when k is much smaller than n. In Java, PriorityQueue is the standard heap-backed collection for this pattern.

Common problem shapes

Top K shows up in many backend and algorithm tasks:

• Find the top 10 most active users.
• Return the 5 largest files.
• Find the 3 most frequent error codes.
• Keep the 100 highest scoring search results.
• Show the most recent events per account.

The important detail is whether you need all items sorted or only the best k items.

Solution 1: sort everything

Sorting is the easiest approach:

List<Integer> values = new ArrayList<>(List.of(7, 1, 9, 3, 5, 8));
values.sort(Comparator.reverseOrder());

List<Integer> top3 = values.subList(0, 3); // [9, 8, 7]

This is clear and often good enough. The cost is O(n log n) because the algorithm sorts every item, even though it only returns k of them.

Use this approach when the input is small, readability matters more than optimization, or the final result must be fully sorted anyway.

Solution 2: keep a min heap of size k

For the largest k values, keep a min heap with at most k elements. The heap root is the smallest item currently in the top group.

public static List<Integer> topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int value : nums) {
        heap.offer(value);

        if (heap.size() > k) {
            heap.poll();
        }
    }

    List<Integer> result = new ArrayList<>(heap);
    result.sort(Comparator.reverseOrder());
    return result;
}

Each insert or remove from a heap of size k costs O(log k). Across n input values, the main loop costs O(n log k).

Read Java PriorityQueue Explained if you want a deeper guide to heap behavior in Java.

Why a min heap finds the largest values

It can feel backwards at first. To find the largest values, why use a min heap?

The heap stores the best k candidates seen so far. The smallest item in that candidate group is the easiest one to replace. When a larger value arrives, it belongs in the group, and the old smallest candidate can be removed.

After scanning the input, the heap contains the largest k values, though not necessarily in sorted output order.

Top K smallest values

For the smallest k values, reverse the idea and use a max heap of size k.

PriorityQueue<Integer> heap =
    new PriorityQueue<>(Comparator.reverseOrder());

Now the heap root is the largest item in the candidate group. If a smaller value arrives, remove the current largest candidate.

Top K frequent elements

Frequency problems add one step: count first, then select top K by count.

public static List<String> topKFrequent(List<String> words, int k) {
    Map<String, Integer> counts = new HashMap<>();

    for (String word : words) {
        counts.merge(word, 1, Integer::sum);
    }

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

    for (Map.Entry<String, Integer> entry : counts.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;
}

The counting step is O(n). The heap step is O(m log k), where m is the number of unique values.

Complexity comparison

Approach	Time complexity	Extra space	Best when
Sort all items	O(n log n)	Depends on sort	Input is small or full sorted order is needed.
Heap of size k	O(n log k)	O(k)	k is much smaller than n.
Count then heap	O(n + m log k)	O(m + k)	Ranking by frequency.

The heap approach is especially useful when streaming data or when keeping all values sorted would waste work.

Common mistakes

The first mistake is using PriorityQueue and expecting iteration order to be sorted. Java’s PriorityQueue only guarantees that peek and poll expose the current priority item. If the final output must be sorted, copy or drain the heap and sort the result.

The second mistake is using the wrong heap direction. For largest k, use a min heap. For smallest k, use a max heap.

The third mistake is ignoring tie rules. If two values have the same score or frequency, decide whether the result should use alphabetical order, smaller ID first, newer timestamp first, or any order.

The fourth mistake is optimizing too early. Sorting may be easier and less error-prone for small inputs.

Backend examples

Top K patterns are not only interview exercises. Backend systems use them for dashboards, logs, rankings, alerts, and recommendations.

If the data already lives in a database, prefer using the database query engine when possible:

SELECT endpoint, COUNT(*) AS error_count
FROM api_logs
WHERE status_code >= 500
GROUP BY endpoint
ORDER BY error_count DESC
LIMIT 10;

Use in-memory heap logic when processing application-level data, stream batches, test fixtures, or already-loaded results.

Related reading

Read Java PriorityQueue Explained for heap operations, Time Complexity of Java Collections for Java collection tradeoffs, and Big-O Notation Explained for complexity fundamentals. For adjacent array patterns, read Sliding Window Algorithm Explained and Two Pointers Algorithm Explained. Use the Big-O Cheat Sheet as a quick reference while comparing sorting and heap solutions. For the full sequence, browse the Algorithms and Complexity Learning Path.