DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master the most common heap-based interview problems: Kth largest element, merge K sorted lists, find median in a stream, and top K frequent elements.
Why Heaps in Interviews?
Heap problems test whether you can identify when partial ordering is sufficient — you do not need full sorting. Whenever a problem asks for "the Kth something," "top K," or "streaming minimum/maximum," your mind should immediately jump to heaps. Let's dive into the four most important patterns.
Problem 1: Kth Largest Element in an Array
Problem: Given an unsorted array, find the Kth largest element. For example, in [3,2,1,5,6,4] with K=2, the answer is 5.
Approach 1: Sort and Index — O(n log n)
The simplest approach. Sort descending and return index K-1. Works but does more work than necessary.
Approach 2: Min-Heap of Size K — O(n log K)
This is the elegant heap solution. Maintain a min-heap of exactly K elements. After processing all elements, the heap root is the Kth largest:
Example
import heapq
def find_kth_largest(nums, k):
# Keep a min-heap of size k
min_heap = nums[:k]
heapq.heapify(min_heap)
for num in nums[k:]:
if num > min_heap[0]: # Larger than smallest in heap
heapq.heapreplace(min_heap, num) # Pop and push in one operation
return min_heap[0]
print(find_kth_largest([3,2,1,5,6,4], 2)) # Output: 5
Why this works: The min-heap of size K always contains the K largest elements seen so far. The smallest among those K elements (the root) is by definition the Kth largest overall.
Space: O(K). If K is small relative to N, this is much better than sorting.
Approach 3: QuickSelect — O(n) Average
Based on the partition step of QuickSort. Average O(n) but worst case O(n²). In practice, randomized QuickSelect is often the fastest:
Example
import random
def quick_select(nums, k):
k = len(nums) - k # Convert to kth smallest
def partition(left, right):
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
pivot = nums[right]
store = left
for i in range(left, right):
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[right] = nums[right], nums[store]
return store
left, right = 0, len(nums) - 1
while True:
pos = partition(left, right)
if pos == k:
return nums[pos]
elif pos < k:
left = pos + 1
else:
right = pos - 1
Problem 2: Merge K Sorted Lists
Problem: Given K sorted linked lists, merge them into one sorted list.
Approach: Min-Heap of K Elements — O(N log K)
At any point, we only need to compare the current heads of all K lists. A min-heap of size K does this efficiently:
python example
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
heap = []
# Initialize heap with head of each list
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
current = dummy
while heap:
val, idx, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.nextKey insight: The idx parameter prevents comparison of ListNode objects when values are equal. The heap never exceeds size K, so each push/pop is O(log K). With N total nodes, the total time is O(N log K).
Alternative approaches:
- Merge lists pairwise (like merge sort): O(N log K) time but simpler code
- Concatenate all and sort: O(N log N) — worse when K << N
Problem 3: Find Median in a Data Stream
Problem: Design a data structure that supports addNum(num) and findMedian() for a continuous stream of numbers.
The Two-Heap Technique
This is a beautiful pattern. Maintain two heaps:
- max-heap (left half): stores the smaller half of numbers
- min-heap (right half): stores the larger half of numbers
The median is either the top of the max-heap (odd count) or the average of both tops (even count).
Example
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (negated values)
self.large = [] # min-heap
def addNum(self, num):
# Always add to max-heap first (negated for max behavior)
heapq.heappush(self.small, -num)
# Ensure max of left <= min of right
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# Balance sizes: left can have at most 1 more than right
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
elif len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2.0
mf = MedianFinder()
mf.addNum(1) # median = 1
mf.addNum(2) # median = 1.5
mf.addNum(3) # median = 2
print(mf.findMedian()) # 2.0
Complexity: addNum is O(log n), findMedian is O(1). Space is O(n).
Why two heaps? The median divides data into two equal halves. If we maintain each half in a heap with the "extremes" facing each other (max of left half, min of right half), the median is always accessible at the tops.
Problem 4: Top K Frequent Elements
Problem: Given an array, return the K most frequent elements. For [1,1,1,2,2,3] with K=2, return [1,2].
Approach 1: Heap — O(n log K)
Count frequencies, then use a min-heap of size K to keep the top K:
Example
from collections import Counter
import heapq
def top_k_frequent(nums, k):
count = Counter(nums)
# Use min-heap of size k
return heapq.nlargest(k, count.keys(), key=count.get)
# Manual implementation for understanding:
def top_k_frequent_manual(nums, k):
count = Counter(nums)
min_heap = []
for num, freq in count.items():
heapq.heappush(min_heap, (freq, num))
if len(min_heap) > k:
heapq.heappop(min_heap)
return [num for freq, num in min_heap]
Approach 2: Bucket Sort — O(n)
Since frequencies range from 1 to n, we can use bucket sort:
Example
def top_k_frequent_bucket(nums, k):
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return result
Pattern Recognition Guide
| Problem Signal | Technique | Heap Type |
|---|---|---|
| "Kth largest/smallest" | Size-K heap | Min-heap for Kth largest |
| "Top K" elements | Size-K heap | Min-heap (keeps K largest) |
| "Merge K sorted" | Size-K heap | Min-heap of heads |
| "Running median" | Two heaps | Max-heap + Min-heap |
| "Closest K points" | Size-K heap | Max-heap by distance |
| "Schedule/intervals" | Event processing | Min-heap by end time |
Practice Problems (by difficulty)
- Easy: Last Stone Weight — max-heap simulation
- Medium: K Closest Points to Origin — min-heap with distance
- Medium: Task Scheduler — greedy with max-heap for frequencies
- Medium: Reorganize String — max-heap to alternate characters
- Hard: Sliding Window Median — two heaps with lazy deletion
- Hard: IPO (LeetCode 502) — two heaps for capital management
Tips for Interviews
- State your approach clearly: "I'll use a min-heap of size K because I only need the K largest elements, and the min-heap root will be my answer."
- Know your language's API: Python's
heapqis min-heap only. Java hasPriorityQueue. C++ haspriority_queue(max by default). - Watch for tiebreakers: When heap elements might be equal, add a sequence number to avoid comparison errors.
- Consider space: A size-K heap uses O(K) space — mention this as an advantage over sorting.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap Interview Problems.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, heaps, heap, problems
Related Data Structures & Algorithms Topics
Continue learning this concept
HeapsHeap Data StructureUnderstand the heap data structure — complete binary tree property, max-heap and min-heap invariants, array representation, and parent/child index formulas.HeapsHeap OperationsMaster core heap operations — insert with bubble-up, delete with bubble-down, heapify individual nodes, and build a heap in O(n) time from an unordered array.HeapsMax-HeapComplete max-heap implementation from scratch — extract-max, increase-key, heap sort connection, and practical applications with full working code.HeapsMin-Heap Implementation and Use CasesComplete guide to min-heap data structure with implementation from scratch, extract-min, decrease-key operations, and connections to DijkstraHeapsPriority Queue using HeapUnderstand the Priority Queue abstract data type, implement it with a binary heap, and explore real-world applications from task scheduling to graph algorithms.ArraysArray Interview Problems and SolutionsSolve classic array problems including rotation, duplicate finding, and subarray challenges.