{"title":"Top K Elements","description":null,"content":"\n[![YouTube Video](https://img.youtube.com/vi/6_v6OoxvMOE/0.jpg)](https://www.youtube.com/watch?v=6_v6OoxvMOE)\n\n\n**Top K Elements** is a super useful pattern to find the K largest, k smallest or K most frequent elements in a dataset.\n\nThis pattern can be applied to problems like:\n\n- Finding the top 5 highest scores in a game leaderboard.\n- or Retrieving the 3 most frequent words in a document.\n\nA straightforward approach to solve these types of problems is to sort the entire dataset and take the first k or last k elements.\n\nBut, this isn’t the most optimal approach since sorting takes O(nlogn) time.\n\nThe **Top K Elements pattern** allows us to solve this problem more optimally using heaps bringing down the time complexity down from O(nlogn) to O(nlogk)\n\nIn this chapter, you'll learn:\n\n- When to use the Top K Elements pattern.\n- How to implement it efficiently in code.\n\n---\n\n# When to Use the Top K Elements Pattern?\n\nHere are some common scenarios where this pattern can be applied:\n\n- Finding the K largest or smallest elements in an array.\n- Identifying the K most frequent or least frequent elements in a dataset.\n- Dynamically maintaining the top K elements in a real-time data stream, like keeping track of the top 10 scores in a live competition.\n\n---\n\n# How to Implement the Top K Elements Pattern?\n\nLets understand this pattern with an example: **Find the top k largest elements in an array.**\n\nSuppose you have an array: \n\n\n\n\nYou need to find the **top 3 largest elements**. The answer would be: `[10, 15, 20]`.\n\nThere are multiple approaches to solve this problem:\n\n### Sorting\n\nThe simplest approach is to sort the array in **descending order** and take the first K elements.\n\n\n```java\npublic void List topKSorting(int[] arr, int k) {\n Integer[] boxedArray = Arrays.stream(arr).boxed().toArray(Integer[]::new);\n Arrays.sort(boxedArray, Collections.reverseOrder());\n \n List result = new ArrayList<>();\n for (int i = 0; i < k && i < boxedArray.length; i++) {\n result.add(boxedArray[i]);\n }\n return result;\n}\n```\n\n```python\ndef top_k_sorting(arr, k):\n # Sort array in descending order\n sorted_arr = sorted(arr, reverse=True)\n \n # Take first K elements\n result = []\n for i in range(min(k, len(sorted_arr))):\n result.append(sorted_arr[i])\n \n return result\n\n# Alternative (more Pythonic)\ndef top_k_sorting_pythonic(arr, k):\n return sorted(arr, reverse=True)[:k]\n```\n\n```cpp\nvector topKSorting(std::vector& arr, int k) {\n // Create a copy and sort in descending order\n vector sortedArr = arr;\n sort(sortedArr.begin(), sortedArr.end(), greater());\n \n // Take first K elements\n vector result;\n for (int i = 0; i < k && i < sortedArr.size(); i++) {\n result.push_back(sortedArr[i]);\n }\n \n return result;\n}\n```\n\n```csharp\npublic List TopKSorting(int[] arr, int k) {\n // Sort array in descending order\n int[] sortedArr = arr.OrderByDescending(x => x).ToArray();\n \n // Take first K elements\n List result = new List();\n for (int i = 0; i < k && i < sortedArr.Length; i++) {\n result.Add(sortedArr[i]);\n }\n \n return result;\n}\n```\n\n```go\nfunc topKSorting(arr []int, k int) []int {\n // Create a copy of the array\n sortedArr := make([]int, len(arr))\n copy(sortedArr, arr)\n \n // Sort in descending order\n sort.Slice(sortedArr, func(i, j int) bool {\n return sortedArr[i] > sortedArr[j]\n })\n \n // Take first K elements\n result := []int{}\n limit := k\n if k > len(sortedArr) {\n limit = len(sortedArr)\n }\n \n for i := 0; i < limit; i++ {\n result = append(result, sortedArr[i])\n }\n \n return result\n}\n```\n\n```rust\nuse std::cmp::Reverse;\n\npub struct Solution;\n\nimpl Solution {\n pub fn top_k_sorting(arr: Vec, k: i32) -> Vec {\n // Sort array in descending order\n let mut sorted_arr = arr;\n sorted_arr.sort_by_key(|&x| Reverse(x));\n \n // Take first K elements\n let mut result = Vec::new();\n let limit = std::cmp::min(k as usize, sorted_arr.len());\n \n for i in 0..limit {\n result.push(sorted_arr[i]);\n }\n \n result\n }\n}\n```\n\n```javascript\nfunction topKSorting(arr, k) {\n // Sort array in descending order\n const sortedArr = [...arr].sort((a, b) => b - a);\n \n // Take first K elements\n const result = [];\n for (let i = 0; i < k && i < sortedArr.length; i++) {\n result.push(sortedArr[i]);\n }\n \n return result;\n}\n```\n\n```typescript\nfunction topKSorting(arr: number[], k: number): number[] {\n // Sort array in descending order\n const sortedArr = [...arr].sort((a, b) => b - a);\n \n // Take first K elements\n const result: number[] = [];\n for (let i = 0; i < k && i < sortedArr.length; i++) {\n result.push(sortedArr[i]);\n }\n \n return result;\n}\n```\n\n\nHowever, sorting the array takes **O(n log n)** time, which can be too slow for large datasets.\n\nSo while sorting works, it’s not the most optimal solution.\n\nInstead, we can use **heap** data structure to solve this problem more efficiently.\n\nThere are two main types of heaps: **max heap** and **min heap**.\n\nIn a max heap, the largest element is at the top and each parent node is larger than its children.\n\nA min heap is the opposite.\n\nThe smallest element is at the top, and every each node is smaller than its children.\n\nThe heap maintains this property whenever we add or remove elements from it.\n\nWe can solve this problem using both types of heaps, but each works a bit differently.\n\nLet’s start with the **max heap** approach.\n\n### Max-Heap\n\nHere’s how it works:\n\n1. Create a max heap out of all the elements in the array.\n 1. This step, called **heapify**, takes **O(n)** time.\n 2. Since Python’s `heapq` module only supports min heaps, we can simulate a max heap by pushing **negative values** into the heap.\n2. **Pop the top K elements** from the heap.\n 1. Popping an element from a heap of size `n` takes **O(log n)** time.\n 2. Since we’re popping K elements, this step takes **O(K log n)** time.\n\n\n```java\npublic void List topKMaxHeap(int[] arr, int k) {\n PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b - a);\n \n for (int num : arr) {\n maxHeap.offer(num);\n }\n \n List result = new ArrayList<>();\n for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {\n result.add(maxHeap.poll());\n }\n return result;\n}\n```\n\n```python\ndef top_k_max_heap(arr, k):\n # Python's heapq only supports min heap, so use negative values for max heap\n max_heap = [-num for num in arr]\n heapq.heapify(max_heap)\n \n result = []\n for i in range(k):\n if max_heap:\n result.append(-heapq.heappop(max_heap))\n \n return result\n```\n\n```cpp\nvector topKMaxHeap(vector& arr, int k) {\n // Create a max heap (default priority_queue is max heap)\n priority_queue maxHeap;\n \n // Add all elements to heap\n for (int num : arr) {\n maxHeap.push(num);\n }\n \n // Extract top K elements\n vector result;\n for (int i = 0; i < k && !maxHeap.empty(); i++) {\n result.push_back(maxHeap.top());\n maxHeap.pop();\n }\n \n return result;\n}\n```\n\n```csharp\npublic List TopKMaxHeap(int[] arr, int k) {\n // Create a max heap using PriorityQueue with reverse comparer\n PriorityQueue maxHeap = new PriorityQueue(\n Comparer.Create((a, b) => b.CompareTo(a))\n );\n \n // Add all elements to heap\n foreach (int num in arr) {\n maxHeap.Enqueue(num, num);\n }\n \n // Extract top K elements\n List result = new List();\n for (int i = 0; i < k && maxHeap.Count > 0; i++) {\n result.Add(maxHeap.Dequeue());\n }\n \n return result;\n}\n```\n\n```go\ntype MaxHeap []int\n\nfunc (h MaxHeap) Len() int { return len(h) }\nfunc (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }\nfunc (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *MaxHeap) Push(x interface{}) {\n *h = append(*h, x.(int))\n}\n\nfunc (h *MaxHeap) Pop() interface{} {\n old := *h\n n := len(old)\n x := old[n-1]\n *h = old[0 : n-1]\n return x\n}\n\nfunc topKMaxHeap(arr []int, k int) []int {\n // Create a max heap\n maxHeap := &MaxHeap{}\n heap.Init(maxHeap)\n \n // Add all elements to heap\n for _, num := range arr {\n heap.Push(maxHeap, num)\n }\n \n // Extract top K elements\n result := []int{}\n for i := 0; i < k && maxHeap.Len() > 0; i++ {\n result = append(result, heap.Pop(maxHeap).(int))\n }\n \n return result\n}\n```\n\n```rust\nuse std::cmp::Reverse;\nuse std::collections::BinaryHeap;\n\npub struct Solution;\n\nimpl Solution {\n pub fn top_k_max_heap(arr: Vec, k: i32) -> Vec {\n // Create a max heap\n let mut max_heap: BinaryHeap = BinaryHeap::new();\n \n // Add all elements to heap\n for num in arr {\n max_heap.push(num);\n }\n \n // Extract top K elements\n let mut result = Vec::new();\n for _ in 0..k {\n if let Some(val) = max_heap.pop() {\n result.push(val);\n } else {\n break;\n }\n }\n \n result\n }\n}\n```\n\n```javascript\nclass MaxHeap {\n constructor() {\n this.heap = [];\n }\n \n push(val) {\n this.heap.push(val);\n this.bubbleUp(this.heap.length - 1);\n }\n \n pop() {\n if (this.heap.length === 0) return null;\n if (this.heap.length === 1) return this.heap.pop();\n \n const max = this.heap[0];\n this.heap[0] = this.heap.pop();\n this.bubbleDown(0);\n return max;\n }\n \n isEmpty() {\n return this.heap.length === 0;\n }\n \n bubbleUp(index) {\n while (index > 0) {\n const parentIndex = Math.floor((index - 1) / 2);\n if (this.heap[index] <= this.heap[parentIndex]) break;\n [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];\n index = parentIndex;\n }\n }\n \n bubbleDown(index) {\n while (true) {\n let largest = index;\n const left = 2 * index + 1;\n const right = 2 * index + 2;\n \n if (left < this.heap.length && this.heap[left] > this.heap[largest]) {\n largest = left;\n }\n if (right < this.heap.length && this.heap[right] > this.heap[largest]) {\n largest = right;\n }\n if (largest === index) break;\n \n [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];\n index = largest;\n }\n }\n}\n\nfunction topKMaxHeap(arr, k) {\n const maxHeap = new MaxHeap();\n \n // Add all elements to heap\n for (const num of arr) {\n maxHeap.push(num);\n }\n \n // Extract top K elements\n const result = [];\n for (let i = 0; i < k && !maxHeap.isEmpty(); i++) {\n result.push(maxHeap.pop());\n }\n \n return result;\n}\n```\n\n```typescript\nclass MaxHeap {\n private heap: number[] = [];\n \n push(val: number): void {\n this.heap.push(val);\n this.bubbleUp(this.heap.length - 1);\n }\n \n pop(): number | null {\n if (this.heap.length === 0) return null;\n if (this.heap.length === 1) return this.heap.pop()!;\n \n const max = this.heap[0];\n this.heap[0] = this.heap.pop()!;\n this.bubbleDown(0);\n return max;\n }\n \n isEmpty(): boolean {\n return this.heap.length === 0;\n }\n \n private bubbleUp(index: number): void {\n while (index > 0) {\n const parentIndex = Math.floor((index - 1) / 2);\n if (this.heap[index] <= this.heap[parentIndex]) break;\n [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];\n index = parentIndex;\n }\n }\n \n private bubbleDown(index: number): void {\n while (true) {\n let largest = index;\n const left = 2 * index + 1;\n const right = 2 * index + 2;\n \n if (left < this.heap.length && this.heap[left] > this.heap[largest]) {\n largest = left;\n }\n if (right < this.heap.length && this.heap[right] > this.heap[largest]) {\n largest = right;\n }\n if (largest === index) break;\n \n [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];\n index = largest;\n }\n }\n}\n\nfunction topKMaxHeap(arr: number[], k: number): number[] {\n const maxHeap = new MaxHeap();\n \n // Add all elements to heap\n for (const num of arr) {\n maxHeap.push(num);\n }\n \n // Extract top K elements\n const result: number[] = [];\n for (let i = 0; i < k && !maxHeap.isEmpty(); i++) {\n const val = maxHeap.pop();\n if (val !== null) {\n result.push(val);\n }\n }\n \n return result;\n}\n```\n\n\nThe **space complexity** of this approach is **O(n)** because we’re adding all the elements to the heap.\n\nNow, let’s look at the more efficient approach using a **min heap**.\n\n### Min-Heap\n\nHere’s how it works:\n\n- Initialize a min heap with the first K elements of the array.\n- Iterate through the rest of the array:\n - If the current element is larger than the root of the heap (since it’s a min heap, the root is the smallest of the K elements)\n - Remove the root and insert the new element.\n - This keeps the heap size at K and ensures it only contains the top K largest elements.\n- After processing all elements, the heap will contain the k largest elements.\n\n\n```java\npublic void List topKMinHeap(int[] arr, int k) {\n PriorityQueue minHeap = new PriorityQueue<>();\n \n // Add first K elements\n for (int i = 0; i < k; i++) {\n minHeap.offer(arr[i]);\n }\n \n // Process remaining elements\n for (int i = k; i < arr.length; i++) {\n if (arr[i] > minHeap.peek()) {\n minHeap.poll();\n minHeap.offer(arr[i]);\n }\n }\n \n return new ArrayList<>(minHeap);\n}\n```\n\n```python\ndef top_k_min_heap(arr, k):\n # Create a min heap with first K elements\n min_heap = arr[:k].copy()\n heapq.heapify(min_heap)\n \n # Process remaining elements\n for i in range(k, len(arr)):\n if arr[i] > min_heap[0]:\n heapq.heappop(min_heap)\n heapq.heappush(min_heap, arr[i])\n \n return min_heap\n```\n\n```cpp\nvector topKMinHeap(vector& arr, int k) {\n // Create a min heap with first K elements\n priority_queue, greater> minHeap;\n \n // Add first K elements\n for (int i = 0; i < k; i++) {\n minHeap.push(arr[i]);\n }\n \n // Process remaining elements\n for (int i = k; i < arr.size(); i++) {\n if (arr[i] > minHeap.top()) {\n minHeap.pop();\n minHeap.push(arr[i]);\n }\n }\n \n // Convert heap to vector\n vector result;\n while (!minHeap.empty()) {\n result.push_back(minHeap.top());\n minHeap.pop();\n }\n \n return result;\n}\n```\n\n```csharp\npublic List TopKMinHeap(int[] arr, int k) {\n // Create a min heap (default PriorityQueue is min heap)\n PriorityQueue minHeap = new PriorityQueue();\n \n // Add first K elements\n for (int i = 0; i < k; i++) {\n minHeap.Enqueue(arr[i], arr[i]);\n }\n \n // Process remaining elements\n for (int i = k; i < arr.Length; i++) {\n if (arr[i] > minHeap.Peek()) {\n minHeap.Dequeue();\n minHeap.Enqueue(arr[i], arr[i]);\n }\n }\n \n // Convert heap to list\n List result = new List();\n while (minHeap.Count > 0) {\n result.Add(minHeap.Dequeue());\n }\n \n return result;\n}\n```\n\n```go\ntype MinHeap []int\n\nfunc (h MinHeap) Len() int { return len(h) }\nfunc (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }\nfunc (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *MinHeap) Push(x interface{}) {\n *h = append(*h, x.(int))\n}\n\nfunc (h *MinHeap) Pop() interface{} {\n old := *h\n n := len(old)\n x := old[n-1]\n *h = old[0 : n-1]\n return x\n}\n\nfunc topKMinHeap(arr []int, k int) []int {\n // Create a min heap with first K elements\n minHeap := &MinHeap{}\n heap.Init(minHeap)\n \n // Add first K elements\n for i := 0; i < k; i++ {\n heap.Push(minHeap, arr[i])\n }\n \n // Process remaining elements\n for i := k; i < len(arr); i++ {\n if arr[i] > (*minHeap)[0] {\n heap.Pop(minHeap)\n heap.Push(minHeap, arr[i])\n }\n }\n \n // Convert heap to slice\n result := make([]int, minHeap.Len())\n copy(result, *minHeap)\n \n return result\n}\n```\n\n```rust\nuse std::cmp::Reverse;\nuse std::collections::BinaryHeap;\n\npub struct Solution;\n\nimpl Solution {\n pub fn top_k_min_heap(arr: Vec, k: i32) -> Vec {\n let k = k as usize;\n \n // Create a min heap with first K elements\n let mut min_heap: BinaryHeap> = BinaryHeap::new();\n \n // Add first K elements\n for i in 0..k {\n min_heap.push(Reverse(arr[i]));\n }\n \n // Process remaining elements\n for i in k..arr.len() {\n if arr[i] > min_heap.peek().unwrap().0 {\n min_heap.pop();\n min_heap.push(Reverse(arr[i]));\n }\n }\n \n // Convert heap to vector\n let mut result = Vec::with_capacity(min_heap.len());\n while let Some(Reverse(x)) = min_heap.pop() {\n result.push(x);\n }\n \n result\n }\n}\n```\n\n```javascript\nclass MinHeap {\n constructor() {\n this.heap = [];\n }\n \n push(val) {\n this.heap.push(val);\n this.bubbleUp(this.heap.length - 1);\n }\n \n pop() {\n if (this.heap.length === 0) return null;\n if (this.heap.length === 1) return this.heap.pop();\n \n const min = this.heap[0];\n this.heap[0] = this.heap.pop();\n this.bubbleDown(0);\n return min;\n }\n \n peek() {\n return this.heap[0];\n }\n \n isEmpty() {\n return this.heap.length === 0;\n }\n \n toArray() {\n return [...this.heap];\n }\n \n bubbleUp(index) {\n while (index > 0) {\n const parentIndex = Math.floor((index - 1) / 2);\n if (this.heap[index] >= this.heap[parentIndex]) break;\n [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];\n index = parentIndex;\n }\n }\n \n bubbleDown(index) {\n while (true) {\n let smallest = index;\n const left = 2 * index + 1;\n const right = 2 * index + 2;\n \n if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {\n smallest = left;\n }\n if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {\n smallest = right;\n }\n if (smallest === index) break;\n \n [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];\n index = smallest;\n }\n }\n}\n\nfunction topKMinHeap(arr, k) {\n const minHeap = new MinHeap();\n \n // Add first K elements\n for (let i = 0; i < k; i++) {\n minHeap.push(arr[i]);\n }\n \n // Process remaining elements\n for (let i = k; i < arr.length; i++) {\n if (arr[i] > minHeap.peek()) {\n minHeap.pop();\n minHeap.push(arr[i]);\n }\n }\n \n return minHeap.toArray();\n}\n```\n\n```typescript\nclass MinHeap {\n private heap: number[] = [];\n \n push(val: number): void {\n this.heap.push(val);\n this.bubbleUp(this.heap.length - 1);\n }\n \n pop(): number | null {\n if (this.heap.length === 0) return null;\n if (this.heap.length === 1) return this.heap.pop()!;\n \n const min = this.heap[0];\n this.heap[0] = this.heap.pop()!;\n this.bubbleDown(0);\n return min;\n }\n \n peek(): number {\n return this.heap[0];\n }\n \n isEmpty(): boolean {\n return this.heap.length === 0;\n }\n \n toArray(): number[] {\n return [...this.heap];\n }\n \n private bubbleUp(index: number): void {\n while (index > 0) {\n const parentIndex = Math.floor((index - 1) / 2);\n if (this.heap[index] >= this.heap[parentIndex]) break;\n [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];\n index = parentIndex;\n }\n }\n \n private bubbleDown(index: number): void {\n while (true) {\n let smallest = index;\n const left = 2 * index + 1;\n const right = 2 * index + 2;\n \n if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {\n smallest = left;\n }\n if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {\n smallest = right;\n }\n if (smallest === index) break;\n \n [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];\n index = smallest;\n }\n }\n}\n\nfunction topKMinHeap(arr: number[], k: number): number[] {\n const minHeap = new MinHeap();\n \n // Add first K elements\n for (let i = 0; i < k; i++) {\n minHeap.push(arr[i]);\n }\n \n // Process remaining elements\n for (let i = k; i < arr.length; i++) {\n if (arr[i] > minHeap.peek()) {\n minHeap.pop();\n minHeap.push(arr[i]);\n }\n }\n \n return minHeap.toArray();\n}\n```\n\n\nLet’s break down the time and space complexity of this approach:\n\n- **Building the initial heap** with K elements takes **O(K)** time.\n- For the remaining `N-K` elements, the **heappushpop** operation takes **O(log K)** time.\n- So, the overall **time complexity** is **O(K + (N-K) log K)**, which simplifies to **O(N log K)**.\n\nThe **space complexity** is **O(K)** because we’re only storing K elements in the heap.\n\nLet’s walk through the min heap approach with the example array and find the top 3 largest elements.\n\n\n\n\n**1. Initialize the min heap with the first 3 elements: [7, 10, 4].**\n\nAfter heapifing it becomes ➔ [4, 10, 7].\n\n\n\n\n**Now process the rest of the array:**\n\n`3` is smaller than `4`, so we skip it.\n\n\n\n\n`20` is greater than `4`, so we remove `4` and insert `20`.\n\n\n\n\n`15` is greater than `7`, so we remove `7` and insert `15`\n\n\n\n\nAfter processing all elements, the heap contains `[10, 15, 20]`, which are the top 3 largest elements.\n\nFor this problem, using a **min heap** is more efficient compared to a max heap, because it only keeps track of K elements at a time, instead of storing all elements in the heap.\n\nHowever, if you need to find the **K smallest elements** instead, you would use a **max heap** approach.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium