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 Union-Find data structure with path compression and union by rank, achieving nearly O(1) operations for connectivity queries.
The Problem
You need to maintain a collection of disjoint sets and support two operations efficiently:
- Find(x): Which set does element x belong to?
- Union(x, y): Merge the sets containing x and y
This comes up constantly: "Are two nodes connected?" "Merge two groups." "How many connected components exist?" Union-Find answers all of these in nearly O(1) per operation.
The Intuition
Think of a collection of friend groups. Initially, everyone is in their own group. When two people become friends, their entire groups merge. Find asks "who is the leader of x's group?" Union merges two groups by connecting their leaders.
We represent each set as a tree. The root of the tree is the set's representative. Find walks up to the root. Union connects one root to another.
Naive Implementation (Slow)
Example
class NaiveUnionFind:
def __init__(self, n):
self.parent = list(range(n)) # Everyone is their own parent
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
self.parent[root_x] = root_y
Problem: Trees can become tall chains → find is O(n) worst case.
Optimization 1: Path Compression
When we call find(x), we walk all the way up to the root. Why not make every node on this path point directly to the root? Next time, find is O(1) for all nodes on that path.
Example
Before find(4): After find(4):
0 0
| / | \
1 1 2 3 4
|
2
|
3
|
4
Optimization 2: Union by Rank
When merging two trees, attach the shorter tree under the taller tree. This keeps trees shallow.
- Rank approximates tree height
- Always make the smaller tree a subtree of the larger tree
- This guarantees tree height stays O(log n)
Optimized Implementation
Example
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # Number of connected components
def find(self, x):
"""Find with path compression."""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""Union by rank. Returns True if merged, False if already connected."""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Attach smaller rank tree under higher rank tree
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1
return True
def connected(self, x, y):
"""Check if x and y are in the same set."""
return self.find(x) == self.find(y)
def num_components(self):
return self.count
C++ Implementation
Example
class UnionFind {
vector<int> parent, rank_;
int components;
public:
UnionFind(int n) : parent(n), rank_(n, 0), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank_[px] < rank_[py]) swap(px, py);
parent[py] = px;
if (rank_[px] == rank_[py]) rank_[px]++;
components--;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int count() { return components; }
};
Dry Run Example
| Initial | [0][1][2][3][4][5][6] (7 components) |
| union(0, 1): merge {0} and {1} | {0,1} |
| union(2, 3): merge {2} and {3} | {2,3} |
| union(4, 5): merge {4} and {5} | {4,5} |
| find(1) | 0 (root of {0,1}) |
| find(3) | 2 (root of {2,3}) |
| union(1, 3): find(1)=0, find(3)=2, merge | {0,1,2,3} |
| union(5, 6): merge {4,5} and {6} | {4,5,6} |
| Components: {0,1,2,3}, {4,5,6} | 2 components |
Time Complexity
With both path compression AND union by rank:
- Find: O(α(n)) amortized — where α is the inverse Ackermann function
- Union: O(α(n)) amortized
- α(n) ≤ 4 for any practical input (n < 10^80)
- Effectively O(1) per operation!
Without optimizations: O(n) worst case per find.
Common Applications
1. Connected Components
python example
def count_components(n, edges):
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.num_components()2. Cycle Detection in Undirected Graph
python example
def has_cycle(n, edges):
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v): # Already connected = cycle!
return True
return False3. Kruskal's MST Algorithm
Union-Find is the backbone of Kruskal's — it checks whether adding an edge would create a cycle.
4. Network Connectivity
"Is server A reachable from server B?" — maintain Union-Find as connections are added.
Advanced: Union-Find with Size
Sometimes you need the size of each component:
Example
class UnionFindWithSize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * 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
# Merge smaller into larger
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
self.size[rx] += self.size[ry]
return True
def get_size(self, x):
return self.size[self.find(x)]
Key Takeaways
- Union-Find is the go-to for dynamic connectivity problems
- Always use both optimizations (path compression + union by rank/size)
- It is NOT good for disconnection operations (splitting sets is hard)
- Operations are amortized O(α(n)) ≈ O(1) in practice
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Union-Find (Disjoint Set Union).
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, graphs, union, find
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsDijkstra\Master Dijkstra\GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsGraph Interview ProblemsMaster 12 essential graph interview problems with clear approaches, patterns, and solutions for coding interviews at top tech companies.