0552MediumArrayTwo PointersMatrixSimulation

Settling the Colour Match Board

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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:

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.
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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def candy_crush(board: list[list[int]]) -> list[list[int]]:

Java

public int[][] candyCrush(int[][] board)

The intended approach

Time O((rows * cols)^2) in the worst case: each round costs O(rows * cols) and at least three pieces leave per round.Space O(rows * cols) for the set of marked cells.

Loop until a round finds nothing. Each round first marks: scan every row left to right grouping equal non-empty neighbours, then scan every column top to bottom the same way, and record the coordinates of every piece in a group of three or more into a set. The marking has to finish before any piece is emptied, otherwise emptying a sideways group would break an upright group that runs through it. Then empty every marked cell and settle each column with two indices: read upward from the bottom and write survivors into the lowest free row, then blank whatever is left above the write position. Every round removes at least three pieces, which bounds how many rounds can happen. Rows are edited in place throughout, and the same board object is returned.

Pythonentry point: candy_crush

def candy_crush(board):
    # Repeat clear-then-drop until a clear pass finds nothing. Marking is done
    # into a separate set before anything is emptied, so a piece that belongs to
    # both a sideways run and an upright run does not knock out the other run
    # while it is still being looked for. The board is edited in place.
    rows = len(board)
    cols = len(board[0])
    while True:
        doomed = set()
        for r in range(rows):
            c = 0
            while c < cols:
                v = board[r][c]
                if v == 0:
                    c += 1
                    continue
                j = c
                while j < cols and board[r][j] == v:
                    j += 1
                if j - c >= 3:
                    for k in range(c, j):
                        doomed.add((r, k))
                c = j
        for c in range(cols):
            r = 0
            while r < rows:
                v = board[r][c]
                if v == 0:
                    r += 1
                    continue
                j = r
                while j < rows and board[j][c] == v:
                    j += 1
                if j - r >= 3:
                    for k in range(r, j):
                        doomed.add((k, c))
                r = j
        if not doomed:
            return board
        for r, c in doomed:
            board[r][c] = 0
        for c in range(cols):
            write = rows - 1
            for r in range(rows - 1, -1, -1):
                if board[r][c] != 0:
                    board[write][c] = board[r][c]
                    write -= 1
            while write >= 0:
                board[write][c] = 0
                write -= 1

The obvious version

Decide cell by cell instead of scanning runs. For each occupied cell, walk outward left and right while the colour matches to measure the sideways run it sits in, then walk up and down to measure the upright run; if either reaches three the cell is marked. Empty all marked cells, then rebuild each column as a list of survivors padded with empties on top, writing it back into the same rows. Repeat while any cell was marked.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_candy_crush(board):
    rows = len(board)
    cols = len(board[0])
    while True:
        hit = set()
        for r in range(rows):
            for c in range(cols):
                v = board[r][c]
                if v == 0:
                    continue
                left = c
                while left - 1 >= 0 and board[r][left - 1] == v:
                    left -= 1
                right = c
                while right + 1 < cols and board[r][right + 1] == v:
                    right += 1
                if right - left + 1 >= 3:
                    hit.add((r, c))
                    continue
                up = r
                while up - 1 >= 0 and board[up - 1][c] == v:
                    up -= 1
                down = r
                while down + 1 < rows and board[down + 1][c] == v:
                    down += 1
                if down - up + 1 >= 3:
                    hit.add((r, c))
        if not hit:
            return board
        for r, c in hit:
            board[r][c] = 0
        for c in range(cols):
            keep = []
            for r in range(rows):
                if board[r][c] != 0:
                    keep.append(board[r][c])
            fresh = [0] * (rows - len(keep)) + keep
            for r in range(rows):
                board[r][c] = fresh[r]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in