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 Union-Find (Disjoint Set Union) in graph contexts — finding connected components, dynamic connectivity queries, cycle detection in undirected graphs, Kruskal
Union-Find Recap
Union-Find (DSU) maintains groups of elements and supports:
- Find(x): Which group is x in? Returns the root/representative.
- Union(x, y): Merge the groups containing x and y.
With path compression + union by rank: O(α(n)) ≈ O(1) per operation.
Example
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return False
if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
self.parent[ry] = rx
self.size[rx] += self.size[ry]
if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
self.components -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
def component_size(self, x):
return self.size[self.find(x)]
Application 2 — Cycle Detection in Undirected Graph
Example
def has_cycle(n, edges):
"""
Detect cycle in undirected graph.
If two vertices being connected are already in the same component → cycle.
Time: O(E α(V))
"""
dsu = DSU(n)
for u, v in edges:
if not dsu.union(u, v): # Already connected → adding this edge creates cycle
return True
return False
print(has_cycle(4, [(0,1),(1,2),(2,3)])) # False — path, no cycle
print(has_cycle(4, [(0,1),(1,2),(2,0)])) # True — triangle
print(has_cycle(5, [(0,1),(1,2),(3,4),(2,3),(1,4)])) # True
Application 3 — Redundant Connection
Example
def find_redundant_connection(edges):
"""
Find the last edge that makes an undirected graph contain a cycle.
(LeetCode 684)
Time: O(n α(n))
"""
n = len(edges)
dsu = DSU(n + 1) # Vertices 1-indexed
for u, v in edges:
if not dsu.union(u, v):
return [u, v] # This edge creates a cycle
return []
print(find_redundant_connection([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])) # [1,4]
Application 4 — Dynamic Connectivity
python example
class DynamicConnectivity:
"""
Support both edge additions and connectivity queries.
No edge removal (for removal, need more complex structures).
"""
def __init__(self, n):
self.dsu = DSU(n)
def add_edge(self, u, v):
self.dsu.union(u, v)
def are_connected(self, u, v):
return self.dsu.connected(u, v)
def num_components(self):
return self.dsu.components
def component_size(self, v):
return self.dsu.component_size(v)
dc = DynamicConnectivity(6)
dc.add_edge(0, 1)
dc.add_edge(2, 3)
print(dc.are_connected(0, 1)) # True
print(dc.are_connected(0, 2)) # False
print(dc.num_components()) # 4
dc.add_edge(1, 2)
print(dc.are_connected(0, 3)) # True (0-1-2-3)
print(dc.num_components()) # 3Application 5 — Largest Component
Example
def largest_component(n, edges):
"""Find size of largest connected component."""
dsu = DSU(n)
for u, v in edges:
dsu.union(u, v)
return max(dsu.component_size(i) for i in range(n))
print(largest_component(6, [(0,1),(1,2),(2,3),(4,5)])) # 4 ({0,1,2,3})
Application 6 — Accounts Merge
Example
from collections import defaultdict
def accounts_merge(accounts):
"""
Merge accounts sharing at least one email.
DSU on email indices.
Time: O(n × m × α(n×m)) where m = avg emails per account.
"""
email_to_id = {}
email_to_name = {}
idx = 0
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = idx
email_to_name[email] = name
idx += 1
dsu = DSU(idx)
for account in accounts:
first_email_id = email_to_id[account[1]]
for email in account[2:]:
dsu.union(first_email_id, email_to_id[email])
# Group emails by root
root_to_emails = defaultdict(set)
for email, eid in email_to_id.items():
root_to_emails[dsu.find(eid)].add(email)
result = []
for root, emails in root_to_emails.items():
any_email = next(iter(emails))
result.append([email_to_name[any_email]] + sorted(emails))
return result
accounts = [
["John","johnsmith@mail.com","john_newyork@mail.com"],
["John","johnsmith@mail.com","john00@mail.com"],
["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]
]
merged = accounts_merge(accounts)
for acc in merged:
print(acc)
DSU vs BFS/DFS for Connected Components
| Feature | DSU | BFS/DFS |
|---|---|---|
| Time per query | O(α(n)) ≈ O(1) | O(V+E) for full traversal |
| Build time | O(E α(V)) | O(V+E) |
| Dynamic edges | ✅ — just call union | ❌ — must rebuild |
| Find path | ❌ — only connectivity | ✅ — can trace path |
| Detect cycles | ✅ | ✅ |
| Space | O(V) | O(V) |
Use DSU when: Only need connectivity (not path), edges are added dynamically. Use BFS/DFS when: Need actual paths, graph is static, need ordering.
Summary
DSU solves graph connectivity problems efficiently:
- Count components: Initialize n components, decrement on each union
- Cycle detection: Edge (u,v) creates cycle iff
find(u) == find(v) - Dynamic edges: Add edge with union, query connectivity with find
- Kruskal's MST: Core data structure for cycle-free edge addition
All operations O(α(n)) — essentially constant for all practical inputs.
*Next Lesson: Graph Interview Problems*
Continue the lesson path
Study next in this module
01GraphsTopological Sorting — DFS and BFS (KahnMaster topological sorting completely — what it is, why it only works on DAGs, DFS-based algorithm with finish times, Kahn02GraphsShortest 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.03GraphsPrimMaster 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