FastPrep
Problem · Matrix

Bubble Explosion

● HardPinterestFULLTIMENEW GRADOA

You are given a board of cells, where each cell contains a bubble represented by an integer color. Two cells are neighbors if they share a side, which means adjacency is only vertical or horizontal.

Perform exactly one bubble explosion using the following rules:

  • A bubble is eligible to explode if it has the same color as bubbles in at least 2 neighboring cells.
  • All eligible bubbles, together with same-colored bubbles in neighboring cells, are marked for explosion.
  • All marked bubbles explode at the same time and are removed from the board, creating empty cells.
  • After the explosion, bubbles above empty cells fall downward until all empty cells are filled from above.

Return the board after the explosion. Use 0 for cells that end up empty.

A solution with time complexity no worse than O(rows2 * cols2) fits within the limit.

Examples
01 · Example 1
bubbles = [[3, 1, 2, 1], [1, 1, 1, 4], [3, 1, 2, 2], [3, 3, 3, 4]]
return = [[0, 0, 0, 1], [0, 0, 0, 4], [0, 0, 2, 2], [3, 0, 2, 4]]

The connected group of 1s in the upper-left area is marked and explodes, together with same-colored neighbors. After those cells are removed, bubbles above empty spaces fall downward within each column. Empty cells are represented by 0.

Constraints
  • 1 <= bubbles.length <= 100
  • 1 <= bubbles[0].length <= 100
  • 1 <= bubbles[i][j] <= 10^4
More Pinterest problems
drafts saved locally
public int[][] bubbleExplosion(int[][] bubbles) {
  // write your code here
}
bubbles[[3, 1, 2, 1], [1, 1, 1, 4], [3, 1, 2, 2], [3, 3, 3, 4]]
expected[[0, 0, 0, 1], [0, 0, 0, 4], [0, 0, 2, 2], [3, 0, 2, 4]]
sign in to submit