Introduction

The Top K Elements Pattern is one of the most popular coding interview patterns used to efficiently find the largest, smallest, most frequent, or closest K elements without sorting the entire dataset.

The pattern primarily uses a Heap (Priority Queue) to maintain only the K most relevant elements.

Instead of sorting all n elements in O(n log n) time, many Top K problems can be solved in O(n log k) time.

---

When Should You Use Top K Elements?

Use this pattern when the problem asks for:

• K Largest Elements
• K Smallest Elements
• K Closest Points
• K Closest Numbers
• Top K Frequent Elements
• Kth Largest Element
• Kth Smallest Element
• Merge K Sorted Lists
• K Closest Values in BST

Typical interview keywords:

• Top K
• Largest
• Smallest
• Closest
• Frequent
• Priority Queue
• Heap
• Kth

---

Basic Idea

Instead of storing every element,

store only the best K candidates.

graph TD
    Read_Element["Read Element"] --> Insert_into_Heap["Insert into Heap"]
    Insert_into_Heap["Insert into Heap"] --> Heap_Size_K["Heap Size  K ?"]
    Heap_Size_K["Heap Size  K ?"] --> Yes["Yes"]
    Yes["Yes"] --> Remove_Lowest_Priority["Remove Lowest Priority"]
    Remove_Lowest_Priority["Remove Lowest Priority"] --> Continue["Continue"]

The heap always contains the current Top K elements.

---

Why Heap?

A Heap allows insertion and deletion in

O(log K)

instead of sorting the entire array.

---

Visualization

Find Top 3 Largest

Input

3 1 8 2 9 6 7

Heap

graph TD
    N_3["3"] --> N_1_3["1 3"]
    N_1_3["1 3"] --> N_1_3_8["1 3 8"]
    N_1_3_8["1 3 8"] --> N_2_3_8["2 3 8"]
    N_2_3_8["2 3 8"] --> N_3_8_9["3 8 9"]
    N_3_8_9["3 8 9"] --> N_6_8_9["6 8 9"]
    N_6_8_9["6 8 9"] --> N_7_8_9["7 8 9"]

Answer

7 8 9

---

Min Heap vs Max Heap

Min Heap

Smallest element stays at the root.

Used for:

• Top K Largest
• K Largest Numbers

graph TD
    N_5_0_0["5"] --> N_8_1_1["8"]
    N_5_0_0["5"] --> N_9_1_2["9"]

---

Max Heap

Largest element stays at the root.

Used for:

• K Smallest
• Largest First Processing

graph TD
    N_20_0_0["20"] --> N_15_1_1["15"]
    N_20_0_0["20"] --> N_12_1_2["12"]

---

Generic Algorithm

graph TD
    Create_Heap["Create Heap"] --> Traverse_Array["Traverse Array"]
    Traverse_Array["Traverse Array"] --> Insert_Element["Insert Element"]
    Insert_Element["Insert Element"] --> Heap_Size_K["Heap Size  K"]
    Heap_Size_K["Heap Size  K"] --> Remove_Root["Remove Root"]
    Remove_Root["Remove Root"] --> Continue["Continue"]
    Continue["Continue"] --> Return_Heap["Return Heap"]

---

Example Problem

Kth Largest Element

Input

[3,2,1,5,6,4]

k = 2

Output

5

---

Java Solution

import java.util.PriorityQueue;

public class KthLargest {

    public static int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> minHeap =
                new PriorityQueue<>();

        for (int num : nums) {

            minHeap.offer(num);

            if (minHeap.size() > k) {

                minHeap.poll();

            }

        }

        return minHeap.peek();

    }

    public static void main(String[] args) {

        int[] nums = {3,2,1,5,6,4};

        System.out.println(findKthLargest(nums,2));

    }

}

Output

5

---

Internal Working

Input

3 2 1 5 6 4

Heap

graph TD
    N_3["3"] --> N_2_3["2 3"]
    N_2_3["2 3"] --> N_1_2_3["1 2 3"]
    N_1_2_3["1 2 3"] --> Remove_1["Remove 1"]
    Remove_1["Remove 1"] --> N_2_3_5["2 3 5"]
    N_2_3_5["2 3 5"] --> Remove_2["Remove 2"]
    Remove_2["Remove 2"] --> N_3_5_6["3 5 6"]
    N_3_5_6["3 5 6"] --> Remove_3["Remove 3"]
    Remove_3["Remove 3"] --> N_4_5_6["4 5 6"]

Root

5

Second largest found.

---

Top K Frequent Elements

Example

Input

1 1 1 2 2 3

K = 2

Frequency Map

1 → 3

2 → 2

3 → 1

Heap

2

1

Output

1 2

---

Complexity Analysis

Operation	Complexity
Heap Insert	O(log K)
Heap Remove	O(log K)
Overall Time	O(n log K)
Space	O(K)

Compared with sorting:

Approach	Complexity
Sorting	O(n log n)
Heap	O(n log K)

When K << n, Heap is much faster.

---

Heap Decision Tree

graph TD
    Need_Largest["Need Largest?"] --> Top_K["Top K?"]
    Top_K["Top K?"] --> Min_Heap["Min Heap"]
    Min_Heap["Min Heap"] --> N_["----------------"]
    N_["----------------"] --> Need_Smallest["Need Smallest?"]
    Need_Smallest["Need Smallest?"] --> Max_Heap["Max Heap"]
    Max_Heap["Max Heap"] --> N_["----------------"]
    N_["----------------"] --> Need_Frequency["Need Frequency?"]
    Need_Frequency["Need Frequency?"] --> HashMap_Heap["HashMap + Heap"]
    HashMap_Heap["HashMap + Heap"] --> N_["----------------"]
    N_["----------------"] --> Need_Closest["Need Closest?"]
    Need_Closest["Need Closest?"] --> Distance_Heap["Distance + Heap"]

---

Common Problems Using Top K Pattern

Problem	Difficulty
Kth Largest Element	Medium
Top K Frequent Elements	Medium
K Closest Points	Medium
K Closest Numbers	Medium
Merge K Sorted Lists	Hard
Kth Smallest in Matrix	Medium
Sort Characters By Frequency	Medium
Frequency Sort	Medium

---

Production Use Cases

Search Engines

Display the top K search results based on ranking scores.

---

E-Commerce

Recommend the top K best-selling products.

---

Banking

Identify the highest-value transactions for fraud analysis.

---

Social Media

Show trending hashtags or the most popular posts.

---

Streaming Platforms

Recommend the top K movies or songs based on user preferences.

---

Cloud Monitoring

Display the top K servers with the highest CPU or memory usage.

---

Analytics

Generate leaderboards and top-performing metrics.

---

AI Recommendation Systems

Return the top K most relevant predictions for a user.

---

Common Mistakes

Using the Wrong Heap

• Top K Largest → Min Heap
• Top K Smallest → Max Heap

---

Sorting Instead of Using Heap

Sorting is slower when only K elements are required.

---

Forgetting Heap Size Check

Always remove the root when:

heap.size() > k

---

Ignoring Duplicate Values

Handle duplicates according to the problem statement.

---

Using PriorityQueue Incorrectly

Remember:

PriorityQueue<Integer>

↓

Min Heap

(Default)

Use a custom comparator for a Max Heap.

---

Interview Tips

Mention these observations:

• Heap maintains only K useful elements.
• Heap size never exceeds K.
• PriorityQueue in Java is a Min Heap by default.
• HashMap + Heap is common for frequency problems.
• O(n log K) is preferred when K is much smaller than n.

---

Frequently Asked Interview Questions

1. What is the Top K Elements pattern?

Answer

It is a pattern that efficiently finds the K largest, smallest, closest, or most frequent elements using a Heap (Priority Queue).

---

2. Why is a Heap used?

Answer

A Heap efficiently maintains only the K required elements while supporting insertion and removal in O(log K) time.

---

3. What is the time complexity?

Answer

Most Top K problems run in O(n log K).

---

4. What is the space complexity?

Answer

Typically O(K) for the heap.

---

5. Why use a Min Heap for Top K Largest elements?

Answer

The smallest element among the current Top K stays at the root, making it easy to remove when a larger element is found.

---

6. Which data structures are commonly used?

Answer

PriorityQueue (Heap), HashMap, Arrays, and occasionally Trees or Graphs.

---

7. Which interview problems commonly use this pattern?

Answer

Kth Largest Element, Top K Frequent Elements, Merge K Sorted Lists, K Closest Points, K Closest Numbers, and Frequency Sort.

---

8. Where is this pattern used in production?

Answer

Search engines, recommendation systems, banking analytics, streaming services, cloud monitoring, fraud detection, and ranking systems.

---

9. What is the biggest mistake candidates make?

Answer

Using the wrong heap type (Min Heap vs Max Heap) or sorting the entire array unnecessarily.

---

10. Why is Top K Elements an important interview pattern?

Answer

Because it teaches efficient partial selection, avoiding unnecessary sorting and optimizing performance for large datasets.

---

Quick Revision

Topic	Summary
Pattern	Top K Elements
Primary Data Structure	Heap (Priority Queue)
Best Complexity	O(n log K)
Space Complexity	O(K)
Min Heap	Top K Largest
Max Heap	Top K Smallest
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• Top K Elements is a fundamental interview pattern centered around Heap (Priority Queue).
• A Heap allows efficient maintenance of only the K most relevant elements.
• Most Top K problems achieve O(n log K) complexity instead of O(n log n) sorting.
• Choosing the correct heap type (Min Heap or Max Heap) is essential for solving these problems correctly.
• This pattern is widely used in search engines, recommendation systems, ranking algorithms, analytics, and cloud monitoring.

---