Union-Find (Disjoint Set)

Q: Which tech companies frequently test Union-Find (Disjoint Set)?

Companies frequently asking Union-Find (Disjoint Set) questions include Google, Amazon, Meta, Microsoft, Uber, Bloomberg.

Q: How do I master the Union-Find (Disjoint Set) pattern?

Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.

Data Structures

Connectivity, cycle detection, and clustering in undirected networks

89 problems·1 Easy·50 Medium·38 Hard

Pattern Study Guide & Cheat Sheet· O(α(N)) ≈ O(1) amortized per operation · O(N) for parent and rank arrays

▼

Disjoint Set Union (DSU) tracks partitions and connectivity of elements, merging groups and querying whether two elements share a component in near-constant O(α(N)) time.

Core Invariant: Maintain representative parent pointers. With Path Compression (`parent[x] = find(parent[x])`) and Union by Rank, tree depth remains <= 4 for all practical universe scales (inverse Ackermann α(N)).

Recognize it (Keywords & Signals)

Connected components in an undirected network
Redundant connection / cycle detection in undirected graph
Number of provinces / islands / friend circles
Graph valid tree (exactly n - 1 edges and 1 connected component)
Minimum Spanning Tree (Kruskal's algorithm)

When NOT to use

Directed graphs (DSU cannot handle edge directions; use Topological Sort or Tarjan / Kosaraju).

How to solve (Step-by-step)

1.Initialize `parent = list(range(n))` and `rank = [1] * n`.
2.Implement `find(x)`: recursively find root while flattening tree (`parent[x] = find(parent[x])`).
3.Implement `union(x, y)`: find roots `rx = find(x)`, `ry = find(y)`. If equal, they already connect (cycle detected!).
4.If unequal, attach smaller rank root under larger rank root, and decrement component count.
5.Return True if merged, False if already connected.

Watch for (Interview Traps)

Comparing raw node IDs instead of representative roots (`x == y` instead of `find(x) == find(y)`)
Omitting path compression: operations degenerate to O(N) linear chains without it
Using DSU on directed graphs where edge orientation matters

Disjoint Set Union (DSU) with Path Compression & Rank

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [1] * size
        self.components = size

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            # Path compression: flatten path directly to root
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # Already in same set (cycle detected!)
            
        # Union by rank: attach smaller tree under larger tree
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            
        self.components -= 1
        return True

Cost: O(α(N)) ≈ O(1) amortized per operation · O(N) for parent and rank arrays (Inverse Ackermann α(N) never exceeds 4 for any practical input size.)

Canonical problems

#547 Number of Provinces: Union cities with direct flights; return final component count

#684 Redundant Connection: First edge where union returns False creates the cycle

#261 Graph Valid Tree: Must have exactly n - 1 edges and 1 connected component

#128 Longest Consecutive Sequence: Union adjacent numbers x and x+1

⌘K

#200Number of Islands

Medium·93 companies·Max freq 100%·Acc 64.7%

RedfinAMDAnduril+90

#128Longest Consecutive Sequence

Medium·49 companies·Max freq 100%·Acc 47.2%

Wissen TechnologyWissen TechnologyNeetCode 150+46

#399Evaluate Division

Medium·25 companies·Max freq 100%·Acc 64.4%

Tower Research CapitalTower Research CapitalUrban Company+22

#695Max Area of Island

Medium·22 companies·Max freq 100%·Acc 74.1%

GrubhubSchlumbergerRoku+19

#827Making A Large Island

Hard·18 companies·Max freq 90%·Acc 56.9%

SnapSnapMoloco+15

#721Accounts Merge

Medium·18 companies·Max freq 83%·Acc 61.7%

GrabDocusignByteDance+15

#130Surrounded Regions

Medium·15 companies·Max freq 87%·Acc 45.8%

PornhubMolocoNeetCode 150+12

#924Minimize Malware Spread

Hard·14 companies·Max freq 100%·Acc 0.4%

DropboxNCRBNY Mellon+11

#1584Min Cost to Connect All Points

Medium·13 companies·Max freq 100%·Acc 71.3%

DirectiNeetCode 150NeetCode 150+10

#694Number of Distinct Islands

Medium·13 companies·Max freq 92%·Acc 62.9%

SnapTikTokSnap+10

#886Possible Bipartition

Medium·13 companies·Max freq 77%·Acc 52.8%

SamsungMeeshoTikTok+10

#261Graph Valid Tree

Medium·12 companies·Max freq 100%·Acc 50.1%

ZenefitsNeetCode 150Blind 75+9

#1319Number of Operations to Make Network Connected

Medium·11 companies·Max freq 100%·Acc 0.7%

Akuna CapitalPhonePeIBM+8

#323Number of Connected Components in an Undirected Graph

Medium·11 companies·Max freq 100%·Acc 65.1%

General MotorsXX+8

#785Is Graph Bipartite?

Medium·11 companies·Max freq 88%·Acc 59.6%

LimeSamsungAmazon+8

#778Swim in Rising Water

Hard·11 companies·Max freq 78%·Acc 68.0%

WeRideNeetCode 150NeetCode 150+8

#684Redundant Connection

Medium·11 companies·Max freq 77%·Acc 67.9%

BoxNeetCode 150NeetCode 150+8

#1202Smallest String With Swaps

Medium·10 companies·Max freq 100%·Acc 60.8%

PhonePePayPalPalantir+7

#305Number of Islands II

Hard·10 companies·Max freq 93%·Acc 40.7%

UberMolocoAurora+7

#2948Make Lexicographically Smallest Array by Swapping Elements

Medium·10 companies·Max freq 75%·Acc 0.7%

PhonePeAtlassianIBM+7

#547Number of Provinces

Medium·9 companies·Max freq 100%·Acc 70.7%

Two SigmaBloombergAmazon+6

#1631Path With Minimum Effort

Medium·9 companies·Max freq 67%·Acc 63.6%

WaymoNutanixVisa+6

#765Couples Holding Hands

Hard·8 companies·Max freq 66%·Acc 0.6%

Squarepoint CapitalConfluentCitadel+5

#2812Find the Safest Path in a Grid

Medium·8 companies·Max freq 62%·Acc 0.6%

ZomatoIntuitUber+5

#990Satisfiability of Equality Equations

Medium·7 companies·Max freq 100%·Acc 52.0%

Sumo LogicSumo LogicCleverTap+4

#3607Power Grid Maintenance

Medium·7 companies·Max freq 75%·Acc 56.1%

CiscoSalesforceZeta Global+4

#1559Detect Cycles in 2D Grid

Medium·6 companies·Max freq 100%·Acc 63.4%

NutanixWeRideAmazon+3

#1905Count Sub Islands

Medium·6 companies·Max freq 100%·Acc 73.0%

XXZepto+3

#3108Minimum Cost Walk in Weighted Graph

Hard·6 companies·Max freq 75%·Acc 68.2%

DE ShawTuringGoogle+3

#2503Maximum Number of Points From Grid Queries

Hard·6 companies·Max freq 75%·Acc 59.2%

JPMorgan ChaseUberAmazon+3

#2493Divide Nodes Into the Maximum Number of Groups

Hard·6 companies·Max freq 63%·Acc 66.9%

UberAccentureGoogle+3

#959Regions Cut By Slashes

Medium·6 companies·Max freq 52%·Acc 77.6%

UberTikTokGoogle+3

#1579Remove Max Number of Edges to Keep Graph Fully Traversable

Hard·6 companies·Max freq 50%·Acc 0.7%

UberDE ShawAmazon+3

#1020Number of Enclaves

Medium·6 companies·Max freq 27%·Acc 72.0%

GoogleBloombergMicrosoft+3

#1267Count Servers that Communicate

Medium·6 companies·Max freq 25%·Acc 73.5%

AmazonGoogleMicrosoft+3

#2492Minimum Score of a Path Between Two Cities

Medium·5 companies·Max freq 100%·Acc 66.2%

UnbxdBloombergGoogle+2

#1061Lexicographically Smallest Equivalent String

Medium·5 companies·Max freq 68%·Acc 81.1%

ClouderaAmazonGoogle+2

#2316Count Unreachable Pairs of Nodes in an Undirected Graph

Medium·5 companies·Max freq 63%·Acc 50.1%

SnapSnapAmazon+2

#1971Find if Path Exists in Graph

Easy·5 companies·Max freq 38%·Acc 55.5%

BloombergMicrosoftAmazon+2

#3532Path Existence Queries in a Graph I

Medium·5 companies·Max freq 38%·Acc 70.7%

GoogleBloombergAmazon+2

#839Similar String Groups

Hard·5 companies·Max freq 38%·Acc 56.4%

DoorDashGoogleApple+2

#1254Number of Closed Islands

Medium·5 companies·Max freq 38%·Acc 67.2%

GoogleOracleMeta+2

#1258Synonymous Sentences

Medium·4 companies·Max freq 100%·Acc 0.6%

CruiseCruiseMoveworks+1

#803Bricks Falling When Hit

Hard·4 companies·Max freq 88%·Acc 0.4%

SnapSnapPhonePe+1

#1722Minimize Hamming Distance After Swap Operations

Medium·4 companies·Max freq 79%·Acc 0.7%

Sumo LogicSumo LogicGoogle+1

#3613Minimize Maximum Component Cost

Medium·4 companies·Max freq 63%·Acc 43.7%

SalesforceAppleGoogle+1

#737Sentence Similarity II

Medium·4 companies·Max freq 50%·Acc 51.4%

RipplingGoogleApple+1

#298Binary Tree Longest Consecutive Sequence

Medium·4 companies·Max freq 50%·Acc 54.8%

TikTokGoogleAmazon+1

#1970Last Day Where You Can Still Cross

Hard·4 companies·Max freq 42%·Acc 68.7%

AtlassianGoogleAmazon+1

#3666Minimum Operations to Equalize Binary String

Hard·4 companies·Max freq 38%·Acc 45.1%

InfosysAmazonGoogle+1

#	Problem	Difficulty	Top Companies↓	Frequency	Acceptance
#200	Number of Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Redfin AMD Anduril Splunk+89	100%	64.7%
#128	Longest Consecutive Sequence ArrayHash TableUnion-Find	Medium	Wissen Technology Wissen Technology NeetCode 150 Blind 75+45	100%	47.2%
#399	Evaluate Division ArrayStringDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryShortest PathBellman–Ford AlgorithmFloyd–Warshall Algorithm	Medium	Tower Research Capital Tower Research Capital Urban Company DP world+21	100%	64.4%
#695	Max Area of Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Grubhub Schlumberger Roku NeetCode 150+18	100%	74.1%
#827	Making A Large Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Hard	Snap Snap Moloco Anduril+14	90%	56.9%
#721	Accounts Merge ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSorting	Medium	Grab Docusign ByteDance Meta+14	83%	61.7%
#130	Surrounded Regions ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Pornhub Moloco NeetCode 150 Nutanix+11	87%	45.8%
#924	Minimize Malware Spread ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph Theory	Hard	Dropbox NCR BNY Mellon Squarepoint Capital+10	100%	0.4%
#1584	Min Cost to Connect All Points ArrayUnion-FindGraph TheoryMinimum Spanning TreePrim's AlgorithmKruskal's AlgorithmBorůvka's Algorithm	Medium	Directi NeetCode 150 PayPay Nutanix+9	100%	71.3%
#694	Number of Distinct Islands ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindSortingMatrixHash Function	Medium	Snap TikTok Snap Coupang+9	92%	62.9%
#886	Possible Bipartition Depth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph ColoringBipartite Graph	Medium	Samsung Meesho TikTok LinkedIn+9	77%	52.8%
#261	Graph Valid Tree Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Zenefits NeetCode 150 Blind 75 Snowflake+8	100%	50.1%
#1319	Number of Operations to Make Network Connected Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Akuna Capital PhonePe IBM PayPal+7	100%	0.7%
#323	Number of Connected Components in an Undirected Graph Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	General Motors X X NeetCode 150+7	100%	65.1%
#785	Is Graph Bipartite? Depth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph ColoringBipartite Graph	Medium	Lime Samsung Amazon Uber+7	88%	59.6%
#778	Swim in Rising Water ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMinimaxHeap (Priority Queue)MatrixDijkstra's Algorithm	Hard	WeRide NeetCode 150 Google Meta+7	78%	68.0%
#684	Redundant Connection Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Box NeetCode 150 InMobi Google+7	77%	67.9%
#1202	Smallest String With Swaps ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSorting	Medium	PhonePe PayPal Palantir Rubrik+6	100%	60.8%
#305	Number of Islands II ArrayHash TableUnion-Find	Hard	Uber Moloco Aurora Waymo+6	93%	40.7%
#2948	Make Lexicographically Smallest Array by Swapping Elements ArrayUnion-FindSorting	Medium	PhonePe Atlassian IBM Goldman Sachs+6	75%	0.7%
#547	Number of Provinces Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Two Sigma Bloomberg Amazon Adobe+5	100%	70.7%
#1631	Path With Minimum Effort ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixDijkstra's Algorithm	Medium	Waymo Nutanix Visa Snowflake+5	67%	63.6%
#765	Couples Holding Hands GreedyDepth-First SearchBreadth-First SearchUnion-FindGraph Theory	Hard	Squarepoint Capital Confluent Citadel Palo Alto Networks+4	66%	0.6%
#2812	Find the Safest Path in a Grid ArrayBinary SearchBreadth-First SearchUnion-FindHeap (Priority Queue)Matrix	Medium	Zomato Intuit Uber Google+4	62%	0.6%
#990	Satisfiability of Equality Equations	Medium	Sumo Logic Sumo Logic CleverTap UiPath+3	100%	52.0%
#3607	Power Grid Maintenance ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryHeap (Priority Queue)Ordered Set	Medium	Cisco Salesforce Zeta Global Amazon+3	75%	56.1%
#1559	Detect Cycles in 2D Grid ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Nutanix WeRide Amazon Google+2	100%	63.4%
#1905	Count Sub Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	X X Zepto DoorDash+2	100%	73.0%
#3108	Minimum Cost Walk in Weighted Graph ArrayBit ManipulationUnion-FindGraph Theory	Hard	DE Shaw Turing Google Amazon+2	75%	68.2%
#2503	Maximum Number of Points From Grid Queries ArrayTwo PointersBreadth-First SearchUnion-FindSortingHeap (Priority Queue)Matrix	Hard	JPMorgan Chase Uber Amazon Google+2	75%	59.2%
#2493	Divide Nodes Into the Maximum Number of Groups Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Hard	Uber Accenture Google Amazon+2	63%	66.9%
#959	Regions Cut By Slashes ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindMatrixPlanar Graph	Medium	Uber TikTok Google Amazon+2	52%	77.6%
#1579	Remove Max Number of Edges to Keep Graph Fully Traversable Union-FindGraph Theory	Hard	Uber DE Shaw Amazon Google+2	50%	0.7%
#1020	Number of Enclaves ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Google Bloomberg Microsoft Uber+2	27%	72.0%
#1267	Count Servers that Communicate ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixCounting	Medium	Amazon Google Microsoft Oracle+2	25%	73.5%
#2492	Minimum Score of a Path Between Two Cities Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Unbxd Bloomberg Google Amazon+1	100%	66.2%
#1061	Lexicographically Smallest Equivalent String StringUnion-Find	Medium	Cloudera Amazon Google Meta+1	68%	81.1%
#2316	Count Unreachable Pairs of Nodes in an Undirected Graph Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Medium	Snap Snap Amazon Google+1	63%	50.1%
#1971	Find if Path Exists in Graph Depth-First SearchBreadth-First SearchUnion-FindGraph Theory	Easy	Bloomberg Microsoft Amazon Google+1	38%	55.5%
#3532	Path Existence Queries in a Graph I ArrayHash TableBinary SearchUnion-FindGraph Theory	Medium	Google Bloomberg Amazon Meta+1	38%	70.7%
#839	Similar String Groups ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-Find	Hard	DoorDash Google Apple Amazon+1	38%	56.4%
#1254	Number of Closed Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix	Medium	Google Oracle Meta Microsoft+1	38%	67.2%
#1258	Synonymous Sentences ArrayHash TableStringBacktrackingSortUnion-Find	Medium	Cruise Cruise Moveworks Rippling	100%	0.6%
#803	Bricks Falling When Hit ArrayUnion-FindMatrix	Hard	Snap Snap PhonePe Google	88%	0.4%
#1722	Minimize Hamming Distance After Swap Operations ArrayDepth-First SearchUnion-Find	Medium	Sumo Logic Sumo Logic Google Bloomberg	79%	0.7%
#3613	Minimize Maximum Component Cost Binary SearchUnion-FindGraph TheorySorting	Medium	Salesforce Apple Google Microsoft	63%	43.7%
#737	Sentence Similarity II ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-Find	Medium	Rippling Google Apple Amazon	50%	51.4%
#298	Binary Tree Longest Consecutive Sequence TreeDepth-First SearchBinary TreeDP on Trees	Medium	TikTok Google Amazon Meta	50%	54.8%
#1970	Last Day Where You Can Still Cross ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMatrix	Hard	Atlassian Google Amazon Meta	42%	68.7%
#3666	Minimum Operations to Equalize Binary String MathStringBreadth-First SearchUnion-FindOrdered Set	Hard	Infosys Amazon Google Microsoft	38%	45.1%

50 displayed (of 50 matching)Filtered: All Companies

Top Companies Testing Union-Find (Disjoint Set)

Browse company-specific interview problem lists and recency breakdowns:

Google Questions Amazon Questions Meta Questions Microsoft Questions Uber Questions Bloomberg Questions