# 14.2 Quick Find

Keeping track of set membership...

Professor Hug's explanation on Quick Find

Intuitively, we might first consider representing Disjoint Sets as a list of sets, e.g,

`List<Set<Integer>>`

.For instance, if we have N=6 elements and nothing has been connected yet, our list of sets looks like:

`[{0}, {1}, {2}, {3}, {4}, {5}, {6}]`

. Looks good. However, consider how to complete an operation like `connect(5, 6)`

. We'd have to iterate through up to `N`

sets to find 5 and `N`

sets to find 6. Our runtime becomes `O(N)`

. And, if you were to try and implement this, the code would be quite complex.The lesson to take away is thatinitial design decisions determine our code complexity and runtime.

Let's consider another approach using a

*single array of integers*.- The
**indices of the array**represent the elements of our set. - The
**value at an index**is the set number it belongs to.

For example, we represent

`{0, 1, 2, 4}, {3, 5}, {6}`

as:
Set 4: {0, 1, 2, 4} | Set 5: {3, 5} | Set 6: {6}

The array indices (0...6) are the elements. The value at

`id[i]`

is the set it belongs to. *The specific set number doesn't matter as long as all elements in the same set share the same id.*Let's see how the connect operation would work. Right now,

`id[2] = 4`

and `id[3] = 5`

. After calling `connect(2, 3)`

, all the elements with id 4 and 5 should have the same id. Let's assign them all the value 5 for now:
Set 5: {0, 1, 2, 3, 4, 5} | Set 6: {6}

`isConnected(x, y)`

To check

`isConnected(x, y)`

, we simply check if `id[x] == id[y]`

. Note this is a constant time operation!
We call this implementation "Quick Find" because finding if elements are connected takes constant time.

public class QuickFindDS implements DisjointSets {

private int[] id;

/* Θ(N) */

public QuickFindDS(int N){

id = new int[N];

for (int i = 0; i < N; i++){

id[i] = i;

}

}

/* need to iterate through the array => Θ(N) */

public void connect(int p, int q){

int pid = id[p];

int qid = id[q];

for (int i = 0; i < id.length; i++){

if (id[i] == pid){

id[i] = qid;

}

}

}

/* Θ(1) */

public boolean isConnected(int p, int q){

return (id[p] == id[q]);

}

}

N = number of elements in our DisjointSets data structure

Implementation | Constructor | `connect` | `isConnected` |

ListOfSets | O(N) | O(N) | |

QuickFind | Θ(N) | Θ(N) | Θ(1) |

1. We didn't discuss this but you can reason that having to create N distinct sets initially is Θ(N) ↩

Last modified 1yr ago