Union-Find

Quick Find

Each element stores a flat component ID. find() is O(1); union() must relabel the entire array — O(n) per call.

Speed

Step 1/0

id[ ] array — component label per element

union(0,1)union(2,3)union(4,5)union(6,7)union(8,9)union(0,2)union(4,6)union(0,4)

…

Complexity

find(x)O(1)

union(p,q)O(n)

SpaceO(n)

n10

Components0

Legend

Scanning

Just updated

Active p or q

Active Recall1/3

What is the time complexity of find() in Quick Find?

Union-Find

Loading visualizer…

Initialize