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 positiondarts[t]
at timet
). You may assume all elements ofdarts
are unique, valid positions within the grid.- It returns an array where the
i
-th element is the number of bubbles that fall after thei
-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.