Candy Crush Board Until Stable
Meta● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given a non-empty rectangular integer matrix board. A positive value is a candy type, and 0 is an empty cell.
On each round, identify every horizontal or vertical run of at least three adjacent cells containing the same positive value. All matches are determined from the board at the start of that round, so overlapping horizontal and vertical runs are crushed simultaneously.
Set every matched cell to 0. Then apply gravity independently in each column: non-zero values fall toward the bottom while preserving their top-to-bottom relative order, and zeros fill the remaining cells at the top.
Repeat matching, crushing, and gravity until the board is stable. Return the stable board.
Function
candyCrushBoard(board: int[][]) → int[][]Examples
Example 1
board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]return = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]Several initial matches are removed, gravity creates additional matches, and the process repeats until the shown board has no horizontal or vertical run of length three.
Example 2
board = [[1,2,3],[4,5,6],[7,8,9]]return = [[1,2,3],[4,5,6],[7,8,9]]The board is already stable, so it is returned unchanged.
Example 3
board = [[1,2,1],[2,2,2],[1,2,1]]return = [[0,0,0],[1,0,1],[1,0,1]]The middle row and middle column overlap. All five matched cells are marked before crushing, and gravity compacts the four corner candies downward.
Constraints
1 <= board.length, board[r].length <= 50.- Every row has the same length.
0 <= board[r][c] <= 2000.- A match contains at least three equal positive values and is horizontal or vertical.