🎒
Technical Interview Study Guide
  • 🍕Welcome!
  • 🍥Getting Started
    • Study Plan
    • Optimizing Revision
    • Summer 2024 Timeline
    • FAQs
  • 🥨Algorithms
    • Binary Search
    • Sorting
    • Recursion
    • Graph
    • Quick Select
    • Intervals
    • Binary
    • Geometry
    • Dynamic Programming
  • 🥞Data Structures
    • Arrays
      • Matrices
    • Strings
    • Linked Lists
      • Doubly Linked Lists
    • Hash Tables
    • Graphs
      • Trees
        • Binary Search Trees
        • Heaps
        • Tries
        • Segment Trees
    • Stacks
    • Queues
      • Double Ended Queues
    • Union-Find Disjoint Set (UFDS)
  • 🍡Problems Guide
    • Dynamic Programming Roadmap
      • Warmup
        • Climbing Stairs
        • Nth Tribonacci Number
        • Perfect Squares
      • Linear Sequence
        • Min Cost to Climb Stairs
        • Minimum Time to Make Rope Colorful
        • House Robber
        • Decode Ways
        • Minimum Cost for Tickets
        • Solving Questions with Brainpower
  • 🍣Other Technical Topics
    • General Problem Solving
    • Runtime Predictions
    • System Design
      • SQL
      • Accessing APIs
    • Operating Systems
  • 🍿Non-technical Topics
    • Behavioral Interviews
    • Resumes
Powered by GitBook
On this page
  • Runtime analysis
  • Implementation
  • Key variables
  • Find with path compression
  • Union by rank
  1. Data Structures

Union-Find Disjoint Set (UFDS)

UFDS is a straightforward but powerful data structure often used to determine when data is in the same set as one another

Runtime analysis

Type
Find(p)
Union(p, q)

Quick Find

O(1)

O(n)

Quick Union

O(n)

O(n)

Weighted union (union by rank)

O(log n)

O(log n)

Path compression

O(log n)

O(log n)

Weighted union + path compression

a(m, n)

a(m, n)

Implementation

Key variables

parent = list(range(n + 1))
rank = [0] * (n + 1)

Find with path compression

def find(p):
	if p == parent[p]:
		return p
	
	parent[p] = find(parent[p])
	return parent[p]

Union by rank

def union(p, q):
	root_p = find(p)
	root_q = find(q)
	if rank[root_p] > rank[root_q]:
		parent[root_q] = root_p
		rank[root_p] += 1
	else:
		parent[root_p] = root_q
		rank[root_q] += 1
PreviousDouble Ended QueuesNextDynamic Programming Roadmap

Last updated 1 year ago

🥞