Jan 25, 2021
1 min read
Top K Numbers
In this blog post, I will be giving a brief introduction on another important data structure pattern that is very important for technical interviews.This pattern is called Top K Numbers. This pattern is very useful to solve the problems that asks to find the top/smallest/frequent K elements in a given set.
The best data structure to keep track of K elements is Heap. The pattern looks like this;
- Based on the problem, insert ‘K’ elements into the min-heap or max-heap.
- Iterate through the remaining numbers, and if you find the number that is larger than what you have in the heap, then remove that number and insert the larger one.
Time Complexity: O(N log K).
Space Complexity: O(K)
References:
