Tracking extremes, medians, and K largest/smallest elements in dynamic streams
Dynamically maintain the K extreme elements using a binary heap, turning an O(N log N) full sort into O(N log K) time.
Core Invariant: The Heap Inversion Principle: To maintain the top K LARGEST elements, use a MIN-heap of size K! The heap root holds the smallest of the top K; if a new element is larger than root, pop root and push new.
K is very close to N (quickselect or full sort is faster and simpler), or random indexed lookups are needed.
import heapq
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
freq_map = Counter(nums)
# Min-heap stores tuples: (frequency, number)
min_heap = []
for num, count in freq_map.items():
heapq.heappush(min_heap, (count, num))
# Keep heap size <= k so root is always the smallest among top k
if len(min_heap) > k:
heapq.heappop(min_heap)
return [num for count, num in min_heap]# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #347 | Top K Frequent Elements ArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect | Medium | 100% | 66.8% | ||
| #23 | Merge k Sorted Lists Linked ListDivide and ConquerHeap (Priority Queue)Merge SortTournament Sort | Hard | 100% | 60.0% | ||
| #239 | Sliding Window Maximum ArrayQueueSliding WindowHeap (Priority Queue)Monotonic QueueRange Minimum/Maximum Query | Hard | 100% | 49.0% | ||
| #253 | Meeting Rooms II ArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum | Medium | 100% | 52.7% | ||
| #295 | Find Median from Data Stream Two PointersDesignSortingHeap (Priority Queue)Data Stream | Hard | 100% | 54.7% | ||
| #215 | Kth Largest Element in an Array ArrayDivide and ConquerSortingHeap (Priority Queue)Quickselect | Medium | 100% | 69.1% | ||
| #621 | Task Scheduler ArrayHash TableGreedySortingHeap (Priority Queue)Counting | Medium | 100% | 63.4% | ||
| #332 | Reconstruct Itinerary ArrayStringDepth-First SearchGraph TheorySortingHeap (Priority Queue)Eulerian CircuitEulerian PathSemi-Eulerian Graph | Hard | 100% | 44.7% | ||
| #692 | Top K Frequent Words ArrayHash TableStringTrieSortingHeap (Priority Queue)Bucket SortCounting | Medium | 100% | 60.4% | ||
| #787 | Cheapest Flights Within K Stops Dynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest Path | Medium | 100% | 42.2% | ||
| #973 | K Closest Points to Origin ArrayMathDivide and ConquerGeometrySortingHeap (Priority Queue)QuickselectK-D Tree | Medium | 100% | 69.2% | ||
| #767 | Reorganize String Hash TableStringGreedySortingHeap (Priority Queue)Counting | Medium | 100% | 57.3% | ||
| #658 | Find K Closest Elements ArrayTwo PointersBinary SearchSliding WindowSortingHeap (Priority Queue) | Medium | 88% | 49.9% | ||
| #1268 | Search Suggestions System ArrayStringBinary SearchTrieSortingHeap (Priority Queue) | Medium | 100% | 65.2% | ||
| #1438 | Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit ArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue | Medium | 100% | 57.8% | ||
| #355 | Design Twitter Hash TableLinked ListDesignHeap (Priority Queue) | Medium | 100% | 45.1% | ||
| #1353 | Maximum Number of Events That Can Be Attended ArrayGreedySortingHeap (Priority Queue) | Medium | 100% | 0.4% | ||
| #407 | Trapping Rain Water II ArrayBreadth-First SearchHeap (Priority Queue)Matrix | Hard | 100% | 0.6% | ||
| #451 | Sort Characters By Frequency Hash TableStringSortingHeap (Priority Queue)Bucket SortCounting | Medium | 88% | 75.5% | ||
| #1046 | Last Stone Weight ArrayHeap (Priority Queue) | Easy | 82% | 66.6% | ||
| #1642 | Furthest Building You Can Reach ArrayGreedyHeap (Priority Queue) | Medium | 100% | 51.0% | ||
| #2402 | Meeting Rooms III ArrayHash TableSortingHeap (Priority Queue)Simulation | Hard | 63% | 0.5% | ||
| #218 | The Skyline Problem ArrayDivide and ConquerBinary Indexed TreeSegment TreeSweep LineSortingHeap (Priority Queue)Ordered Set | Hard | 100% | 0.5% | ||
| #703 | Easy | 93% | 61.3% | |||
| #759 | Employee Free Time ArraySweep LineSortingHeap (Priority Queue) | Hard | 75% | 73.0% | ||
| #642 | Design Search Autocomplete System StringDepth-First SearchDesignTrieSortingHeap (Priority Queue)Data Stream | Hard | 75% | 50.0% | ||
| #743 | Network Delay Time Depth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest PathDijkstra's Algorithm | Medium | 100% | 61.0% | ||
| #378 | Kth Smallest Element in a Sorted Matrix ArrayBinary SearchSortingHeap (Priority Queue)Matrix | Medium | 100% | 0.7% | ||
| #1094 | Car Pooling ArraySortingHeap (Priority Queue)SimulationPrefix Sum | Medium | 89% | 56.4% | ||
| #480 | Sliding Window Median ArrayHash TableSliding WindowHeap (Priority Queue)Treap | Hard | 69% | 39.0% | ||
| #632 | Smallest Range Covering Elements from K Lists ArrayHash TableGreedySliding WindowSortingHeap (Priority Queue) | Hard | 100% | 70.2% | ||
| #778 | Swim in Rising Water ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMinimaxHeap (Priority Queue)MatrixDijkstra's Algorithm | Hard | 78% | 68.0% | ||
| #373 | Find K Pairs with Smallest Sums ArrayHeap (Priority Queue) | Medium | 56% | 42.1% | ||
| #2551 | Put Marbles in Bags ArrayGreedySortingHeap (Priority Queue) | Hard | 50% | 0.7% | ||
| #862 | Shortest Subarray with Sum at Least K ArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic Queue | Hard | 100% | 0.3% | ||
| #1464 | Maximum Product of Two Elements in an Array ArraySortingHeap (Priority Queue) | Easy | 89% | 83.6% | ||
| #1631 | Path With Minimum Effort ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixDijkstra's Algorithm | Medium | 67% | 63.6% | ||
| #264 | Ugly Number II Hash TableMathDynamic ProgrammingHeap (Priority Queue) | Medium | 64% | 49.7% | ||
| #1405 | Longest Happy String StringGreedyHeap (Priority Queue) | Medium | 100% | 65.5% | ||
| #1383 | Maximum Performance of a Team ArrayGreedySortingHeap (Priority Queue) | Hard | 100% | 47.8% | ||
| #3650 | Minimum Cost Path with Edge Reversals Graph TheoryHeap (Priority Queue)Shortest Path | Medium | 89% | 61.8% | ||
| #871 | Minimum Number of Refueling Stops ArrayDynamic ProgrammingGreedyHeap (Priority Queue) | Hard | 79% | 41.6% | ||
| #1834 | Single-Threaded CPU ArraySortingHeap (Priority Queue) | Medium | 75% | 47.8% | ||
| #2812 | Find the Safest Path in a Grid ArrayBinary SearchBreadth-First SearchUnion-FindHeap (Priority Queue)Matrix | Medium | 62% | 57.2% | ||
| #2530 | Maximal Score After Applying K Operations ArrayGreedyHeap (Priority Queue) | Medium | 100% | 64.1% | ||
| #855 | Exam Room DesignHeap (Priority Queue)Ordered Set | Medium | 100% | 0.4% | ||
| #3170 | Lexicographically Minimum String After Removing Stars Hash TableStringStackGreedyHeap (Priority Queue) | Medium | 100% | 51.0% | ||
| #1696 | Jump Game VI ArrayDynamic ProgrammingQueueHeap (Priority Queue)Monotonic Queue | Medium | 100% | 46.5% | ||
| #1648 | Sell Diminishing-Valued Colored Balls ArrayMathBinary SearchGreedySortingHeap (Priority Queue) | Medium | 100% | 0.3% | ||
| #2054 | Two Best Non-Overlapping Events ArrayBinary SearchDynamic ProgrammingSortingHeap (Priority Queue) | Medium | 100% | 64.0% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Tracking extremes, medians, and K largest/smallest elements in dynamic streams It is categorized under Data Structures and features 194 curated interview problems across Easy (15), Medium (105), and Hard (74) difficulties.
Companies frequently asking Top K Elements & Priority Queues questions include Google, Amazon, Meta, Microsoft, Bloomberg, Uber.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.