> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.2-quick-find.md).

# 14.2 Quick Find

{% embed url="<https://www.youtube.com/watch?v=W6Dckcv8PIo&ab_channel=JoshHug>" %}
Professor Hug's explanation on Quick Find
{% endembed %}

### List of Sets

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 that **initial design decisions determine our code complexity and runtime.**

### Quick Find

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:<br>

<figure><img src="/files/82QHyK0p7Lh5D1BBIcfY" alt=""><figcaption><p>Set 4: {0, 1, 2, 4} | Set 5: {3, 5} | Set 6: {6}</p></figcaption></figure>

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.*

### **`connect(x, y)`**

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:<br>

<figure><img src="/files/9goSenveWQsPIEbPrEwC" alt=""><figcaption><p>Set 5: {0, 1, 2, 3, 4, 5} | Set 6: {6}</p></figcaption></figure>

**`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.

### Code & Runtimes

```java
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<br>

| Implementation | Constructor    | `connect` | `isConnected` |
| -------------- | -------------- | --------- | ------------- |
| ListOfSets     | Θ(N)[¹](#note) | O(N)      | O(N)          |
| QuickFind      | Θ(N)           | Θ(N)      | Θ(1)          |

### Note

1\. We didn't discuss this but you can reason that having to create N distinct sets initially is Θ(N)[ ↩](https://joshhug.gitbooks.io/hug61b/content/chap9/chap92.html#reffn_1)