# [Coursera Algorithms I: Week 1] Quick Find and Quick Union in Java

## tl;dr

- What is Quick Find
- Programming Quick Find in Java
- What is Quick Union
- Programming Quick Union in Java

Let me give a big shout out to Coursera’s Algorithm I course currently running right now. I went through week 1 lecture material that covered, topics in union find and analyzing algorithm. In this blog post, I will focus on the first part, union find.

## Union Find

Say there are N nodes in a given set. What kind of data structure would it take to represent that these nodes are connected to one another? What kind of algorithm would we need to use to connect one node to another? What do we do to check if two nodes are connect? These questions will be answered through learning about quick find and quick union implementations of union find.

## Quick Find

Quick find is an algorithm that places emphasis on finding out if two nodes are connected or not. We can use a typical array to represent a set of nodes and their connections to each other.

Indexes of the array are the nodes and the values of the array are the connections. When the value of one index equals that of another node’s value, then the two nodes are connected.

Quick Find approach has a very fast method to check connectivity. To check the connectivity, you just need to access the array twice. However, union is extremely slow. Since whenever you do union, you have to go through all the array, you will end up with O(N) runtime.

The quick find has 3 methods. They are:

- constructor: prepares the set as an array
- connected: checks if two nodes are connected or not
- union: connects two nodes

###To run this java program

- Compile the program.
`javac QuickFind.java`

- Run the compiled program.
`java QuickFind`

## Quick Union

Quick union improves greatly in union operation. Instead of going through entire array during union, you attach one node’s root to another’s root.

### Edited on Feb 11, 2014

- Code for
`QuickUnion.java`

and`QuickFind.java`

were updated to fix some bugs