19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements

45 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements

> DSA Blind 75 Notes by Rishabh - Topic 19

---

### 1. The Top-K Golden Rule (Min-Heap of Size K 👑)

> **The Big Tech Rule:**
> * To find **$K$-th Largest Element** $\rightarrow$ Maintain a **Min-Heap of size $K$**!
> * To find **$K$-th Smallest Element** $\rightarrow$ Maintain a **Max-Heap of size $K$**!

---

### 2. LeetCode #215: Kth Largest Element in an Array ($O(N \log K)$)

```python
import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap) # Discard smaller elements!
            
    return min_heap[0] # ⚡ Root holds the K-th largest element!
```
*Time Complexity:* $O(N \log K)$ (Much faster than $O(N \log N)$ sorting when $K \ll N$).

---

### 3. LeetCode #347: Top K Frequent Elements ($O(N)$ Bucket Sort)

```python
from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums) # num -> frequency
    # Bucket where index = frequency:
    buckets = [[] for _ in range(len(nums) + 1)]
    
    for num, freq in count.items():
        buckets[freq].append(num)
        
    res = []
    # Traverse buckets in reverse (Highest frequency first):
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res
    return res
```
*Time Complexity:* $O(N)$ Linear Time, *Space Complexity:* $O(N)$.

---

### 4. Master Comparison Matrix

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **QuickSelect algorithm Kth largest element me $O(N)$ average time kaise achieve karti hai?** -> QuickSort ke partition step ke baad sirf us specific half me recurse karti hai jisme $K$-th index lie karta hai ($N + \frac{N}{2} + \frac{N}{4}... = 2N = O(N)$).
2. **Kth Largest element me size $K$ ka Min-Heap kyu use hota hai, Max-Heap kyu nahi?** -> Kyunki Min-Heap ke top par $K$ elements me se sabse chhota (i.e. $K$-th largest overall) rehta hai aur purane chhote elements $O(\log K)$ me pop ho jaate hain.
3. **Merge K Sorted Lists (LeetCode #23) me Min-Heap kaise use hoti hai?** -> Heap me har list ka current head node daal dete hain aur min pop karke uska next node heap me push karte rehte hain.

---
**Next Topic:** 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track