AlgoMaster Newsletter

AlgoMaster Newsletter

Share this post

AlgoMaster Newsletter
AlgoMaster Newsletter
LeetCode Pattern - Top 'K' Elements
User's avatar
Discover more from AlgoMaster Newsletter
Master Coding and System Design Interviews. Level up your Software Engineering career. Subscribe and get a FREE System Design Interview Handbook in your inbox.
Over 100,000 subscribers
Already have an account? Sign in

LeetCode Pattern - Top 'K' Elements

Ashish Pratap Singh's avatar
Ashish Pratap Singh
Jul 12, 2025
5

Share this post

AlgoMaster Newsletter
AlgoMaster Newsletter
LeetCode Pattern - Top 'K' Elements
Share

The Top K Elements pattern is frequently used in coding interviews to solve problems that require finding the k largest, smallest, or most frequent elements in a dataset.

This pattern leverages data structures like heaps (priority queues) and sorting algorithms to achieve efficient solutions.

In this blog, we'll explore the concept of the Top K Elements pattern, its importance, and dive into various problems that can be solved using this technique.

Key Data Structure: Heap

A heap is a specialized tree-based data structure that satisfies the heap property.

In a max heap, for any given node, the node's value is greater than or equal to the values of its children. In a min heap, the node's value is less than or equal to the values of its children.

Heaps are particularly useful for Top K problems because:

  1. They maintain elements in a partially sorted order.

  2. They allow for efficient insertion and removal of the top element.

  3. They can be used to find the kth largest/smallest element in O(n log k) time.

Common Approaches

  1. Using a Min Heap for Top K Largest Elements:

    • Maintain a min heap of size k.

    • Iterate through all elements, adding each to the heap.

    • If the heap size exceeds k, remove the smallest element.

    • At the end, the heap contains the k largest elements.

  2. Using a Max Heap for Top K Smallest Elements:

    • Similar to the above, but use a max heap instead.

  3. QuickSelect Algorithm:

    • Based on the partitioning step of QuickSort.

    • Can find the kth largest/smallest element in O(n) average time complexity.

LeetCode Examples

1. Kth Largest Element in an Array (LeetCode 215)

Problem: Given an integer array nums and an integer k, return the kth largest element in the array.

Solution:

  • Use a Min-Heap to keep track of the top K largest elements.

  • Iterate through the array, adding elements to the heap.

  • If the heap size exceeds K, remove the smallest element.

  • The root of the heap will be the Kth largest element.

Code:

Time Complexity: O(n log k)

Space Complexity: O(k)

Subscribe to receive new articles every week.

2. Top K Frequent Elements (LeetCode 347)

Problem Statement: Given an array of integers nums and an integer k, return the k most frequent elements.

Solution:

  1. Use a hashmap to count the frequency of each element.

  2. Use a Min-Heap to keep track of the top K frequent elements.

  3. Iterate through the frequency map, adding elements to the heap.

  4. If the heap size exceeds K, remove the least frequent element.

  5. Extract the elements from the heap.

Code:

Time Complexity: O(n log k)

Space Complexity: O(n)

3. K Closest Point to Origin (LeetCode 973)

Problem Statement: Given an array of points represented as [x, y] coordinates and an integer k, return the k closest points to the origin (0, 0).

Solution:

  1. Use a Max-Heap to keep track of the top K closest points.

  2. Calculate the Euclidean distance for each point.

  3. Add the distance and point to the heap.

  4. If the heap size exceeds K, remove the farthest point.

  5. Extract the points from the heap.

Code:

Time Complexity: O(n log k)

Space Complexity: O(n)

The Top K Elements pattern is a powerful technique for solving a wide range of problems efficiently.

Key points to remember:

  1. Heaps are often the go-to data structure for these problems, offering O(n log k) time complexity.

  2. For finding just the kth element, QuickSelect can provide O(n) average time complexity.

  3. These techniques are particularly useful when k is significantly smaller than n, as they avoid the need to fully sort the data.


Thank you so much for reading.

If you found it valuable, hit a like ❤️ and consider subscribing for more such content every week.

If you have any questions or suggestions, leave a comment.

This post is public so feel free to share it.

Share

Subscribe for free to receive new posts and support my work.

Checkout my Youtube channel for more in-depth content.

Follow me on LinkedIn and X to stay updated.

Checkout my GitHub repositories for free interview preparation resources.

I hope you have a lovely day!

See you soon,

Ashish

5

Share this post

AlgoMaster Newsletter
AlgoMaster Newsletter
LeetCode Pattern - Top 'K' Elements
Share
© 2025 Ashish Pratap Singh
Privacy ∙ Terms ∙ Collection notice
Start writingGet the app
Substack is the home for great culture

Share