
LeetCode Pattern - Top 'K' Elements
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:
They maintain elements in a partially sorted order.
They allow for efficient insertion and removal of the top element.
They can be used to find the kth largest/smallest element in O(n log k) time.
Common Approaches
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.
Using a Max Heap for Top K Smallest Elements:
Similar to the above, but use a max heap instead.
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 k
th 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)
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:
Use a hashmap to count the frequency of each element.
Use a Min-Heap to keep track of the top K frequent elements.
Iterate through the frequency map, adding elements to the heap.
If the heap size exceeds K, remove the least frequent element.
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:
Use a Max-Heap to keep track of the top K closest points.
Calculate the Euclidean distance for each point.
Add the distance and point to the heap.
If the heap size exceeds K, remove the farthest point.
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:
Heaps are often the go-to data structure for these problems, offering O(n log k) time complexity.
For finding just the kth element, QuickSelect can provide O(n) average time complexity.
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.
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