Show problems as
Classic problem #723MediumArrayTwo PointersMatrixSimulation

Candy Crush

Real-world version: Settling the Colour Match Board
Tracked in this browser only
Read Candy Crush on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A puzzle board is given as board, a rectangle of cells. board[i][j] is the colour code of the piece resting in row i and column j, where row 0 is the top row. A value of 0 means the cell is empty; the starting board has no empty cells.

The board settles by repeating these two steps until a round changes nothing:

  1. Clear. Look for every group of three or more pieces of one colour standing side by side in a row, and every group of three or more of one colour standing one above another in a column. Every piece in any such group is removed, and all removals happen together, so a piece that belongs to both a sideways group and an upright group is still found by both.
  2. Drop. In each column, every piece that survives falls straight down until it rests on the bottom of the board or on another piece, keeping the column's surviving pieces in their original top-to-bottom order. The cells above them become empty.

Carry the settling out in place on board, changing the given rows rather than building a new rectangle, and return board once no further round changes anything.

Examples

Example 1

Input
board = [[3, 7, 7], [3, 2, 7], [3, 2, 2], [4, 2, 5]]
Output
[[0, 0, 7], [0, 0, 7], [0, 0, 2], [4, 7, 5]]

Column 0 holds three 3s in rows 0 to 2 and column 1 holds three 2s in rows 1 to 3, so those six pieces go. The 4 in column 0 and the 7 in column 1 then drop to the bottom row, and the resulting board has no group of three left.

Example 2

Input
board = [[1, 2, 1, 4], [2, 2, 2, 4], [1, 2, 1, 4], [3, 5, 6, 7]]
Output
[[0, 0, 0, 0], [1, 0, 1, 0], [1, 0, 1, 0], [3, 5, 6, 7]]

Row 1 holds three 2s across columns 0 to 2, column 1 holds three 2s down rows 0 to 2, and column 3 holds three 4s down rows 0 to 2. The 2 at row 1 column 1 belongs to two of those groups and is removed once. After the survivors drop, no group of three remains.

Example 3

Input
board = [[4, 1, 1], [4, 2, 1], [5, 5, 5], [4, 3, 2]]
Output
[[0, 0, 0], [0, 1, 1], [0, 2, 1], [0, 3, 2]]

The three 5s in row 2 go first. The three 4s in column 0 then sit on rows 1, 2 and 3, so a second round removes them, and after that round nothing more matches.

Constraints

  • rows == board.length
  • cols == board[i].length
  • 3 <= rows, cols <= 50
  • 1 <= board[i][j] <= 2000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def candy_crush(board: list[list[int]]) -> list[list[int]]:
Java
public int[][] candyCrush(int[][] board)

More on the same topics