Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets and Modified Binary Search patterns and today, we will introduce Top K Numbers pattern which is very useful to solve the problems that asks us to find the top / smallest / frequent K elements among a given set.
We are going to use Heap data structure to keep track of K elements.
Problem: Binary Search
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Input: [3, 2, 1, 5, 6, 4] and k = 2 Output: 5
Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4 Output: 4
You may assume k is always valid, 1 ≤ k ≤ array’s length.
Top K Numbers Solution
The best data structure to keep track of top K elements is Heap.
- Take out the smallest number from the heap
- Insert the larger number into the heap
from heapq import * class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: min_heap =  for i in range(k): heappush(min_heap, nums[i]) for i in range(k, len(nums)): if nums[i] > min_heap: heappop(min_heap) heappush(min_heap, nums[i]) return min_heap
Time Complexity: O(N log K).
Space Complexity: O(K)
How to identify?
If the problem asking us to find the top / smallest / frequent K elements among a given set, we need to think about Top K Numbers pattern.
While solving the problems, we are going to use Heap data structure to keep track of K elements.