Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
A

Anonymous

· 3 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.

Reading Progress

0%

Vote for new content