## Introduction

In this lab, you’ll play with the **Disjoint Sets** data structure and solve a
cool problem with it. Hopefully you’ll gain a better understanding of
Disjoint Sets and the ways you can use them!

## The Problem

Alice and Bob are strolling somewhere in a high cloudy place, where sticky
bubbles are hanging from the ceiling. Your assignment is to complete the
`BubbleGrid`

class in order to help them figure out how many bubbles will drop
as they pop them.

#### Representing Bubbles

Bubbles are stored in a 2-D array of 1’s and 0’s. A 1 indicates there is a bubble at that position in the grid, and a 0 indicates there is a space. A bubble will fall if is not “stuck.”

A bubble is stuck if

- It is in the topmost row of the grid,
*or* - It is orthogonally adjacent to a bubble that is stuck.

Alice and Bob decide to throw a sequence of darts. If a dart hits a bubble, it pops, possibly causing some bubbles to fall. If it hits an empty space, nothing happens.

#### Your Task

Each `BubbleGrid`

instance is bound to a single grid, which is passed in
through its constructor; you may assume this grid is valid (i.e. no
floating unstuck bubbles). You must implement the method
`int[] popBubbles(int[][] darts)`

, such that

`darts`

is an array of 2-element arrays representing the grid positions (in`[row, column]`

format) at which darts are thrown in sequence (i.e. a dart is thrown at position`darts[t]`

at time`t`

). You may assume all elements of`darts`

are unique, valid positions within the grid.- It returns an array where the
`i`

-th element is the number of bubbles that fall after the`i`

-th dart is thrown (popped bubbles do not fall!).

You will probably want to use a union-find data structure to solve this problem.
We’ve given you the Lab 6
skeleton for `UnionFind.java`

, in case you’d like to implement it yourself, but
feel free to simply use Princeton’s `WeightedQuickUnionUF`

(`edu.princeton.cs.algs4.WeightedQuickUnionUF`

) instead. You may use it as-is or
create a modified version by extending it in `UnionFind.java`

. Note that your
`UnionFind`

API doesn’t have to match the skeleton’s: you may add/remove methods
as you see fit. We will grade you based on your `popBubbles`

implementation.

** Extra Challenge**: There are a few ways of solving this problem; can you solve
it using only one union-find instance?

#### Example

Given the `grid`

```
[[1, 1, 0],
[1, 0, 0],
[1, 1, 0],
[1, 1, 1]]
```

and `darts`

```
[[2, 2], [2, 0]]
```

`popBubbles()`

should return

```
[0, 4]
```

## Credits

This lab was derived from a problem originally found on Leetcode, contributed by Alex Wice.