• Introduction
• The Problem
  • Representing Bubbles
  • Your Task
  • Example
• Credits

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.