Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Introduction to Union Find Pattern

Union Find, also known as Disjoint Set Union (DSU), is a data structure that keeps track of a partition of a set into disjoint subsets (meaning no set overlaps with another). It provides two primary operations: find, which determines which subset a particular element is in, and union, which merges two subsets into a single subset. This pattern is particularly useful for problems where we need to find whether 2 elements belong to the same group or need to solve connectivity-related problems in a graph or tree.

Core Operations of Union-Find (Disjoint Set Union - DSU):

1

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

Hi design gurus,

You explored a number of different options for optimizing union and find operations, but I don't feel these optimizations were properly contextualized.

For instance, from your article it seems like you could optimize both the union and the find operations simultaneously, but optimizing them at the same time doesn't work because changing parents in the find optimization invalidates the state in the rank or the size arrays.

I would like to see better explanations of these optimizations, how to employ them, and their effects on the time complexity. Also, what is the time complexity of the un-optimized operations? This information is missing too.

L

lejafilip

· 2 years ago

as above

S

sagarbpatil007

· 2 years ago

The amortized time complexity for find and union operations is order of the inverse of Akermann function (which in near constant) I am unsure how we came to this conclusion or calculated the time complexity. can someone please explain?

Show 1 reply
A

akshayavb99

· a year ago

Since naive implementation uses a recursive function call to find the parent, and in the worst case the function is called n times. In this case, wouldn't the space complexity be O(n) instead of O(1)?