DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL 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 — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete 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
Solve 8 classic heap interview problems — kth largest, top K frequent words, merge K lists, reorganize string, IPO (max capital), find median from data stream, smallest range covering K lists, and minimum cost to connect ropes.
Problem 1 — Kth Largest Element in Stream
Problem: Design a class to find the kth largest element in a stream.
Example
import heapq
class KthLargest:
"""
Min-heap of size k: root is the kth largest.
add(): push new element, pop if size > k. O(log k).
"""
def __init__(self, k, nums):
self.k = k
self.heap = []
for num in nums:
self.add(num)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0] # Root = kth largest
kth = KthLargest(3, [4, 5, 8, 2])
print(kth.add(3)) # 4
print(kth.add(5)) # 5
print(kth.add(10)) # 5
print(kth.add(9)) # 8
print(kth.add(4)) # 8
Problem 3 — Merge K Sorted Lists
python example
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __lt__(self, other):
return self.val < other.val # For heap comparison
def merge_k_lists(lists):
"""
Merge k sorted linked lists. O(n log k).
Push heads of all lists into min-heap.
Always extract minimum, add its next node.
"""
heap = []
for head in lists:
if head:
heapq.heappush(heap, head)
dummy = ListNode(0)
current = dummy
while heap:
node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, node.next)
return dummy.nextProblem 4 — Reorganize String
Problem: Rearrange string so no two adjacent characters are the same. Return "" if impossible.
Example
import heapq
from collections import Counter
def reorganize_string(s):
"""
Greedy: always place the most frequent remaining character.
Use max-heap to get most frequent character.
O(n log n) where n = len(s).
"""
freq = Counter(s)
max_heap = [(-count, char) for char, count in freq.items()]
heapq.heapify(max_heap)
result = []
prev_count, prev_char = 0, '' # Track previous character
while max_heap:
count, char = heapq.heappop(max_heap)
if char == prev_char:
# Cannot use most frequent — must use second most frequent
if not max_heap:
return "" # Impossible
count2, char2 = heapq.heappop(max_heap)
result.append(char2)
if count2 + 1 < 0: # Still has remaining instances
heapq.heappush(max_heap, (count2 + 1, char2))
heapq.heappush(max_heap, (count, char)) # Push back original
else:
result.append(char)
prev_count, prev_char = count, char
if count + 1 < 0:
heapq.heappush(max_heap, (count + 1, char))
return ''.join(result)
print(reorganize_string("aab")) # "aba"
print(reorganize_string("aaab")) # ""
Problem 5 — IPO (Maximize Capital)
Problem: Given k projects with profits and capital requirements, start with initial capital w and select at most k projects to maximize final capital.
Example
import heapq
def find_maximized_capital(k, w, profits, capital):
"""
Greedy: always pick the most profitable project we can currently afford.
Min-heap for capital (to find available projects efficiently).
Max-heap for profits (to always pick highest profit available).
O(n log n + k log n)
"""
projects = sorted(zip(capital, profits)) # Sort by capital requirement
available = [] # Max-heap of profits
i = 0
for _ in range(k):
# Add all projects we can now afford
while i < len(projects) and projects[i][0] <= w:
heapq.heappush(available, -projects[i][1]) # Max-heap
i += 1
if not available:
break # Can't afford any more projects
w += -heapq.heappop(available) # Execute most profitable
return w
print(find_maximized_capital(2, 0, [1,2,3], [0,1,1])) # 4
print(find_maximized_capital(3, 0, [1,2,3], [0,1,2])) # 6
Problem 6 — Smallest Range Covering K Lists
Problem: Given k sorted lists, find the smallest range [a,b] such that each list has at least one element in [a,b].
Example
import heapq
def smallest_range(nums):
"""
Use min-heap with one element from each list.
Track current range [min_val, max_val].
Advance the minimum element's list to shrink range.
O(n log k) where n = total elements.
"""
# Initialize: first element from each list
heap = [(row[0], i, 0) for i, row in enumerate(nums)]
heapq.heapify(heap)
current_max = max(row[0] for row in nums)
best = [heap[0][0], current_max]
while True:
current_min, list_idx, elem_idx = heapq.heappop(heap)
# Check if current range is better
if current_max - current_min < best[1] - best[0]:
best = [current_min, current_max]
# Advance to next element in the same list
if elem_idx + 1 == len(nums[list_idx]):
break # This list is exhausted — can't cover all lists
next_val = nums[list_idx][elem_idx + 1]
current_max = max(current_max, next_val)
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return best
print(smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))
# [20, 24]
Problem 7 — Minimum Cost to Connect Ropes
Problem: Given ropes of different lengths, find minimum cost to connect all. Cost of connecting two ropes = sum of their lengths.
Example
import heapq
def connect_ropes(lengths):
"""
Greedy: always combine two shortest ropes.
Min-heap to get two shortest in O(log n) each time.
O(n log n) total.
"""
heapq.heapify(lengths)
total_cost = 0
while len(lengths) > 1:
first = heapq.heappop(lengths)
second = heapq.heappop(lengths)
cost = first + second
total_cost += cost
heapq.heappush(lengths, cost)
return total_cost
print(connect_ropes([4, 3, 2, 6])) # 29
# (2+3)=5, (4+5)=9, (6+9)=15 → total = 5+9+15 = 29
Problem 8 — Find Median from Data Stream
Example
import heapq
class MedianFinder:
"""
Two heaps approach: O(log n) add, O(1) findMedian.
"""
def __init__(self):
self.low = [] # Max-heap: lower half (negate values)
self.high = [] # Min-heap: upper half
def add_num(self, num):
heapq.heappush(self.low, -num)
# Ensure all low ≤ all high
if self.high and -self.low[0] > self.high[0]:
heapq.heappush(self.high, -heapq.heappop(self.low))
# Balance sizes
if len(self.low) > len(self.high) + 1:
heapq.heappush(self.high, -heapq.heappop(self.low))
elif len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def find_median(self):
if len(self.low) == len(self.high):
return (-self.low[0] + self.high[0]) / 2
return float(-self.low[0])
mf = MedianFinder()
for n in [5, 15, 1, 3]:
mf.add_num(n)
print(mf.find_median())
# 5, 10.0, 5, 4.0
Pattern Summary
| Problem | Heap Type | Key Pattern |
|---|---|---|
| Kth Largest Stream | Min-heap (size k) | Root = kth largest |
| Top K Frequent Words | Max-heap | Freq-word tuples for ordering |
| Merge K Lists | Min-heap | Always extract current minimum |
| Reorganize String | Max-heap | Greedy: most frequent first |
| IPO | Min-heap + Max-heap | Unlock projects, pick best profit |
| Smallest Range | Min-heap | Advance minimum to shrink range |
| Connect Ropes | Min-heap | Huffman-style greedy |
| Median Stream | Two heaps | Balance lower/upper halves |
Heap problems follow this pattern: Repeatedly identify an extreme (minimum or maximum) of a changing set, process it, and update the set. A heap makes each "find + remove + add" sequence O(log n).
*Heaps section complete. Moving to Trees.*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap Problems — 8 Classic Interview Problems with Complete Solutions.
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 — Complete Introduction to the Priority-Based Tree Data StructureA thorough introduction to heaps — what a heap is, the complete binary tree property, min-heap and max-heap definitions, the heap property with visual examples, heap vs BST, array representation with index formulas, real-world applications, and a roadmap through all heap operations.HeapsHeap Operations — Complete Reference with Complexity AnalysisComplete reference for all heap operations — push, pop, peek, heapify, decrease/increase key, delete arbitrary, merge heaps, and find Kth element. Each operation explained with algorithm, step-by-step trace, implementation, and formal complexity proof.HeapsMax Heap — Complete Implementation and ApplicationsMaster the max-heap with complete implementation — insert with sift-up, extract maximum with sift-down, Python workaround using negation, in-place heap sort, max-heap for sliding window maximum, and the kth largest element problem.HeapsMin Heap — Complete Implementation with All OperationsMaster the min-heap data structure with complete from-scratch implementation — insert with sift-up, extract minimum with sift-down, decrease key, delete arbitrary element, build heap in O(n), and heap sort. All operations with detailed traces and complexity analysis.HeapsPriority Queue Using Heap — Implementation, Applications, and PatternsMaster priority queues built on heaps — complete Python and Java implementations, DijkstraArraysArray Interview Problems — 15 Classic Problems with Complete SolutionsSolve 15 classic array interview problems that appear at top tech companies. Each problem includes the problem statement, multiple approaches from brute force to optimal, step-by-step solution explanation, complete code, and time/space complexity analysis.