# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.2-quick-find.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.