FastPrepFastPrep
Problem Brief

Bubble Explosion

FULLTIMENEW 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.

1Example 1

Input
bubbles = [[3, 1, 2, 1], [1, 1, 1, 4], [3, 1, 2, 2], [3, 3, 3, 4]]
Output
[[0, 0, 0, 1], [0, 0, 0, 4], [0, 0, 2, 2], [3, 0, 2, 4]]
Explanation

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

Limits and guarantees your solution can rely on.

  • 1 <= bubbles.length <= 100
  • 1 <= bubbles[0].length <= 100
  • 1 <= bubbles[i][j] <= 10^4
public int[][] bubbleExplosion(int[][] bubbles) {
  // write your code here
}
Input

bubbles

[[3, 1, 2, 1], [1, 1, 1, 4], [3, 1, 2, 2], [3, 3, 3, 4]]

Output

[[0, 0, 0, 1], [0, 0, 0, 4], [0, 0, 2, 2], [3, 0, 2, 4]]

Sign in to submit your solution.