Himanshu's Blog

Union-Find (or Disjoint Set) is a data structure used to manage disjoint sets of elements through two primary operations: find(x) and union(A, B). The find(x) operation determines which set the element $x$ belongs to, while the union(A, B, C) operation merges the sets $A$ and $B$ into a single set $C$. In this article, we will explore Robert Endre Tarjan’s work on determining the upper bound of the time complexity for these Union-Find operations.

The Problem:

1. To find square of a number and add one.
2. Add logs to the see how the result is formed.
3. Should be able to add more functions easily like multiplyThree.
4. Functions defined should be composable in any order (we can multiplyThree before addOne or vice versa).

We will solve this problem using a monad design pattern in a step by step thought process.