DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Disjoint Set Union (DSU) - Union Find

Master DSU with path compression and union by rank for efficient operations.

What is Disjoint Set Union?

Disjoint Set Union (DSU), also called Union-Find, is a data structure that tracks a collection of non-overlapping (disjoint) sets. It supports two primary operations extremely efficiently: finding which set an element belongs to, and merging two sets into one. Think of it like managing groups of friends — you can quickly check if two people are in the same friend group, and you can merge two friend groups together.

The beauty of DSU is that with two simple optimizations (path compression and union by rank), both operations run in nearly O(1) time — technically O(α(n)) where α is the inverse Ackermann function, which is effectively constant for any practical input size.

Naive Implementation

The simplest approach uses a parent array where each element points to its parent:

Example

class NaiveDSU: def __init__(self, n): self.parent = list(range(n)) # Each element is its own parent def find(self, x): """Find root of x by following parent pointers""" while self.parent[x] != x: x = self.parent[x] return x def union(self, x, y): """Merge sets containing x and y""" root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_x] = root_y def connected(self, x, y): return self.find(x) == self.find(y)

Problem: Without optimizations, the tree can become a long chain, making Find operation O(n) in the worst case.

Optimized Implementation with Path Compression and Union by Rank

Example

class DSU: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n self.size = [1] * n self.num_components = n def find(self, x): """Find with path compression""" if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # Path compression return self.parent[x] def union(self, x, y): """Union by rank""" root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False # Already in same set # Attach smaller tree under root of larger tree if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 self.num_components -= 1 return True def connected(self, x, y): return self.find(x) == self.find(y) def get_size(self, x): return self.size[self.find(x)] # Usage Example dsu = DSU(7) # 7 elements: 0,1,2,3,4,5,6 dsu.union(0, 1) # {0,1} {2} {3} {4} {5} {6} dsu.union(2, 3) # {0,1} {2,3} {4} {5} {6} dsu.union(0, 3) # {0,1,2,3} {4} {5} {6} print(dsu.connected(1, 2)) # True (same group) print(dsu.connected(1, 4)) # False (different groups) print(dsu.num_components) # 4 components remain print(dsu.get_size(0)) # 4 (size of component containing 0)

How Path Compression Works

Path compression flattens the tree structure during Find operations. When you find the root of an element, you make every node along the path point directly to the root:

Before path compression (finding root of 4)

After find(4) with path compression

/ | | \

1 2 3 4

Now future Find operations on any of these elements take O(1) since they point directly to the root.

How Union by Rank Works

Union by rank ensures we always attach the shorter tree under the root of the taller tree. This prevents the tree from growing unnecessarily tall:

Example

Without union by rank (worst case): With union by rank: 0 0 | / | \ 1 1 2 3 | / \ 2 4 5 | 3 Height = n Height = O(log n)

Java Implementation

Example

public class DSU { private int[] parent, rank, size; private int components; public DSU(int n) { parent = new int[n]; rank = new int[n]; size = new int[n]; components = n; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // Path compression return parent[x]; } public boolean union(int x, int y) { int rootX = find(x), rootY = find(y); if (rootX == rootY) return false; if (rank[rootX] < rank[rootY]) { int t = rootX; rootX = rootY; rootY = t; } parent[rootY] = rootX; size[rootX] += size[rootY]; if (rank[rootX] == rank[rootY]) rank[rootX]++; components--; return true; } public boolean connected(int x, int y) { return find(x) == find(y); } public int getComponents() { return components; } }

Complexity Analysis

Operation	Naive	With Union by Rank	With Both Optimizations
Find	O(n)	O(log n)	O(α(n)) ≈ O(1)
Union	O(n)	O(log n)	O(α(n)) ≈ O(1)
Space	O(n)	O(n)	O(n)

α(n) is the inverse Ackermann function — it grows so slowly that for any practical input (even 10^80 elements), α(n) ≤ 4. Effectively constant time.

Classic Applications

1. Kruskal's Minimum Spanning Tree

Example

def kruskal_mst(edges, n): """Find MST using DSU""" edges.sort(key=lambda e: e[2]) # Sort by weight dsu = DSU(n) mst = [] for u, v, weight in edges: if not dsu.connected(u, v): dsu.union(u, v) mst.append((u, v, weight)) if len(mst) == n - 1: break return mst

2. Detecting Cycles in Undirected Graphs

python example

def has_cycle(edges, n):
    dsu = DSU(n)
    for u, v in edges:
        if dsu.connected(u, v):
            return True  # Edge connects two nodes already in same component
        dsu.union(u, v)
    return False

3. Number of Connected Components

python example

def count_components(edges, n):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return dsu.num_components

Real-World Applications

Social networks — finding friend groups, suggesting connections
Image processing — connected component labeling in pixel grids
Network connectivity — determining if all nodes can reach each other
Percolation theory — modeling fluid flow through porous materials
Game development — merging regions in procedural map generation
Database systems — equivalence class determination in query optimization

Interview Questions

Q1: What is the time complexity of DSU with both optimizations? A: O(α(n)) per operation, where α is the inverse Ackermann function. For all practical purposes, this is O(1).

Q2: Can you undo union operations in DSU? A: Standard DSU does not support undo. However, a "DSU with rollback" variant stores history on a stack and can reverse unions. This is used in offline divide-and-conquer problems.

Q3: How would you find the number of connected components? A: Maintain a counter initialized to n (number of elements). Decrease by 1 on each successful union. The counter always holds the current component count.

Q4: How is DSU used in Kruskal's algorithm? A: Sort edges by weight. For each edge, check if its endpoints are in the same component (Find). If not, add the edge to MST and merge components (Union). This greedily builds the MST.

Q5: What is the difference between union by rank and union by size? A: Union by rank attaches the shorter tree under the taller one (based on tree height). Union by size attaches the smaller set under the larger one (based on element count). Both achieve O(log n) height. Combined with path compression, both give O(α(n)).

Key Takeaways

DSU is the go-to data structure for dynamic connectivity problems
Path compression and union by rank together give nearly O(1) per operation
It is essential for Kruskal's MST, cycle detection, and connected components
The implementation is short (under 30 lines) but incredibly powerful
Learn to recognize problems that ask "are these connected?" — they usually need DSU

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Disjoint Set Union (DSU) - Union Find.

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, advanced, topics, disjoint

Related Data Structures & Algorithms Topics

Continue learning this concept

Advanced TopicsBit Manipulation - Advanced TechniquesMaster bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.Advanced TopicsBloom Filter - Probabilistic Data StructureLearn about Bloom filters, a space-efficient probabilistic data structure for set membership testing with constant-time operations.Advanced TopicsComputational Geometry - Algorithms and TechniquesMaster computational geometry concepts, geometric algorithms, and problem-solving techniques.Advanced TopicsRandomized Algorithms - Probabilistic ComputingExplore randomized algorithms and probabilistic approaches.Advanced TopicsSkip List - Probabilistic Balanced StructureLearn skip lists as probabilistic alternative to balanced trees.Advanced TopicsSuffix Array - String IndexingEfficient string indexing and pattern matching with suffix arrays.

PreviousComputational Geometry - Algorithms and Techniques NextRandomized Algorithms - Probabilistic Computing

DSA Notes

Disjoint Set Union (DSU) - Union Find

Master DSU with path compression and union by rank for efficient operations.

What is Disjoint Set Union?

Naive Implementation

The simplest approach uses a parent array where each element points to its parent:

Example

Problem: Without optimizations, the tree can become a long chain, making Find operation O(n) in the worst case.

Optimized Implementation with Path Compression and Union by Rank

Example

How Path Compression Works

Path compression flattens the tree structure during Find operations. When you find the root of an element, you make every node along the path point directly to the root:

Before path compression (finding root of 4)

After find(4) with path compression

/ | | \

1 2 3 4

Now future Find operations on any of these elements take O(1) since they point directly to the root.

How Union by Rank Works

Union by rank ensures we always attach the shorter tree under the root of the taller tree. This prevents the tree from growing unnecessarily tall:

Example

Without union by rank (worst case): With union by rank: 0 0 | / | \ 1 1 2 3 | / \ 2 4 5 | 3 Height = n Height = O(log n)

Java Implementation

Example

Complexity Analysis

Operation	Naive	With Union by Rank	With Both Optimizations
Find	O(n)	O(log n)	O(α(n)) ≈ O(1)
Union	O(n)	O(log n)	O(α(n)) ≈ O(1)
Space	O(n)	O(n)	O(n)

α(n) is the inverse Ackermann function — it grows so slowly that for any practical input (even 10^80 elements), α(n) ≤ 4. Effectively constant time.

Classic Applications

1. Kruskal's Minimum Spanning Tree

Example

2. Detecting Cycles in Undirected Graphs

python example

def has_cycle(edges, n):
    dsu = DSU(n)
    for u, v in edges:
        if dsu.connected(u, v):
            return True  # Edge connects two nodes already in same component
        dsu.union(u, v)
    return False

3. Number of Connected Components

python example

def count_components(edges, n):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return dsu.num_components

Real-World Applications

Social networks — finding friend groups, suggesting connections
Image processing — connected component labeling in pixel grids
Network connectivity — determining if all nodes can reach each other
Percolation theory — modeling fluid flow through porous materials
Game development — merging regions in procedural map generation
Database systems — equivalence class determination in query optimization

Interview Questions

Q1: What is the time complexity of DSU with both optimizations? A: O(α(n)) per operation, where α is the inverse Ackermann function. For all practical purposes, this is O(1).

Key Takeaways

DSU is the go-to data structure for dynamic connectivity problems
Path compression and union by rank together give nearly O(1) per operation
It is essential for Kruskal's MST, cycle detection, and connected components
The implementation is short (under 30 lines) but incredibly powerful
Learn to recognize problems that ask "are these connected?" — they usually need DSU

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Disjoint Set Union (DSU) - Union Find.

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, advanced, topics, disjoint

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousComputational Geometry - Algorithms and Techniques NextRandomized Algorithms - Probabilistic Computing