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
Master topological sorting completely — what it is, why it only works on DAGs, DFS-based algorithm with finish times, Kahn
What Is Topological Sorting?
A topological ordering of a directed graph is an ordering of vertices such that for every directed edge (u, v), vertex u appears before vertex v in the ordering.
Requirements:
- The graph must be a DAG (Directed Acyclic Graph)
- Only directed graphs have topological orderings
Course prerequisites (DAG)
Math101 → Math201 → Math301
↑
CS101 → CS201
Valid topological orders
Math101, CS101, CS201, Math201, Math301
CS101, Math101, CS201, Math201, Math301
CS101, CS201, Math101, Math201, Math301
All orders respect: prerequisite always comes before dependent course.
Algorithm 2 — Kahn's Algorithm (BFS + In-Degrees)
Key insight: In any valid topological ordering, vertices with no predecessors must come first. Process them, remove their edges, repeat.
Example
from collections import deque, defaultdict
def kahn_topological_sort(graph, n_vertices):
"""
Kahn's BFS-based topological sort.
Time: O(V + E), Space: O(V + E)
Returns topological order or detects cycle.
"""
# Count in-degrees for all vertices
in_degree = defaultdict(int)
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# Start with all vertices that have no prerequisites
queue = deque([v for v in graph if in_degree[v] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v) # All prerequisites met
if len(result) != len(graph):
raise ValueError("Graph has a cycle — topological sort not possible")
return result
graph = {
'Math101': ['Math201'],
'CS101': ['CS201'],
'CS201': ['Math201'],
'Math201': ['Math301'],
'Math301': []
}
print(kahn_topological_sort(graph, 5))
Step-by-step trace:
| In-degrees | Math101:0, CS101:0, CS201:1, Math201:2, Math301:1 |
| Queue | [Math101, CS101] (in-degree 0) |
| Step 1: Dequeue Math101. Remove edge Math101 | Math201. |
| Math201 in-degree | 2-1=1 |
| Queue | [CS101] |
| Step 2: Dequeue CS101. Remove CS101 | CS201. |
| CS201 in-degree: 1-1=0 | Add to queue |
| Queue | [CS201] |
| Step 3: Dequeue CS201. Remove CS201 | Math201. |
| Math201 in-degree: 1-1=0 | Add to queue |
| Queue | [Math201] |
| Step 4: Dequeue Math201. Remove Math201 | Math301. |
| Math301 in-degree: 1-1=0 | Add to queue |
| Queue | [Math301] |
| Step 5 | Dequeue Math301. |
| Queue | [] |
| Result | [Math101, CS101, CS201, Math201, Math301] ✓ |
DFS vs Kahn's Comparison
| Feature | DFS | Kahn's (BFS) |
|---|---|---|
| Algorithm type | Recursive DFS | Iterative BFS |
| Cycle detection | GRAY vertex → cycle | len(result) < V → cycle |
| Implementation | Clean with recursion | Explicit in-degree tracking |
| Unique ordering | Depends on DFS order | Depends on queue ordering |
| Parallelism | Harder to parallelize | Easier (process 0-in-degree at same time) |
Applications
Course Schedule (LeetCode 207 & 210)
Example
def can_finish(num_courses, prerequisites):
"""Can you finish all courses given prerequisites?"""
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
count = 0
while queue:
u = queue.popleft()
count += 1
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return count == num_courses # True if no cycle
print(can_finish(2, [[1,0]])) # True
print(can_finish(2, [[1,0],[0,1]])) # False (cycle!)
def find_order(num_courses, prerequisites):
"""Return valid course completion order."""
graph = defaultdict(list)
in_degree = [0] * num_courses
for c, p in prerequisites:
graph[p].append(c); in_degree[c] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
order = []
while queue:
u = queue.popleft(); order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return order if len(order) == num_courses else []
Build System (Compile Order)
Example
def build_order(projects, dependencies):
"""
Given list of projects and dependencies (a must be built before b),
find valid build order.
"""
graph = defaultdict(list)
in_degree = {p: 0 for p in projects}
for a, b in dependencies:
graph[a].append(b)
in_degree[b] += 1
result = kahn_topological_sort(dict(graph), len(projects))
return result
projects = ['A','B','C','D','E','F']
deps = [('A','D'),('F','B'),('B','D'),('F','A'),('D','C')]
print(build_order(projects, deps))
Lexicographically Smallest Topological Order
Example
import heapq
def lex_topological_sort(graph):
"""
Kahn's algorithm using min-heap instead of queue
→ always processes smallest vertex among those with 0 in-degree.
"""
in_degree = defaultdict(int)
for u in graph:
for v in graph[u]: in_degree[v] += 1
heap = [v for v in graph if in_degree[v] == 0]
heapq.heapify(heap)
result = []
while heap:
u = heapq.heappop(heap)
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
heapq.heappush(heap, v)
return result
Summary
Topological sort orders vertices of a DAG such that all edges go "forward":
- DFS approach: Add to result after finishing, reverse the result
- Kahn's (BFS): Process 0-in-degree vertices, decrement neighbors' in-degrees
- Cycle detection: GRAY vertex (DFS) or
len(result) < V(Kahn's) - Time: O(V + E) for both approaches
Use when: Task scheduling, course prerequisites, build systems, dependency resolution, compiler compilation order.
*Next Lesson: Shortest Path Algorithms*
Continue the lesson path
Study next in this module
01GraphsShortest Path Algorithms — Complete Comparison and Selection GuideMaster all shortest path algorithms — BFS for unweighted graphs, Dijkstra for non-negative weights, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, DAG shortest paths, A* heuristic search, and a decision guide for choosing the right algorithm for every scenario.02GraphsUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivityMaster Union-Find (Disjoint Set Union) in graph contexts — finding connected components, dynamic connectivity queries, cycle detection in undirected graphs, Kruskal03GraphsPrimMaster Prim04GraphsMinimum Spanning Tree — Definition, Properties, and ApplicationsMaster Minimum Spanning Tree concepts completely — what an MST is, the cut property and cycle property proofs, why MSTs are optimal, the two fundamental MST algorithms (Kruskal