> For the complete documentation index, see [llms.txt](https://blog.sunilgudivada.dev/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/union-find-data-structure/quick-find-lazy-approach.md).

# Quick Find - Lazy Approach

## Quick Union - Lazy Approach

Integer array `id[]` of length `N`.

**Interpretation**: `id[i]` is parent of `i`.

Root of `i` is `id[id[id[...id[i]...]]]`.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-05bfdb7e65b084b45e54112d12d1935ddad2d425%2Fimage%20\(20\).png?alt=media)

After`union(3,5)`

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-42dfdefdda3c6bd57f98b418bb6a6a43e3faa8e2%2Fimage%20\(1\).png?alt=media)

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-abdc3b7dcca2914dccd1e88646256be242bd0e6f%2Fimage%20\(7\).png?alt=media)

### Java Implementation

```java
public class QuickUnionUF 
{
   private int[] id;
   
   // set id of each object to itself (N array accesses)
   public QuickUnionUF(int N)
   {
      id = new int[N];
      for (int i = 0; i < N; i++) id[i] = i;
   }
   
   // chase parent pointers until reach root (depth of i array accesses)
   private int root(int i)
   {
      while (i != id[i]) i = id[i];
      return i; 
   }
   
   // check if p and q have same root (depth of p and q array accesses)
   public boolean connected(int p, int q)
   {
      return root(p) == root(q);
   }
   
   // change root of p to point to root of q (depth of p and q array accesses)
   public void union(int p, int q)
   {
      int i = root(p);
      int j = root(q);
      id[i] = j;
   }
}
```

##