Challenge Lab 6: Falling Bubbles


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

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

You will probably want to use a union-find data structure to solve this problem. We’ve given you the Lab 6 skeleton for, 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 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?


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]


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