LeetCode 723: Candy Crush

Problem Restatement

We are given an m x n board of candies.

Each cell contains either:

Value	Meaning
Positive integer	A candy type
`0`	Empty cell

The board represents the game state after a move.

We need to repeatedly apply these rules until the board becomes stable:

If three or more candies of the same type are adjacent horizontally or vertically, crush all of them at the same time.
Crushed candies become empty cells.
Candies above empty cells fall down.
Repeat until no more candies can be crushed.

Return the stable board. The board dimensions are between 3 and 50, and initial candy values are positive integers.

Input and Output

Item	Meaning
Input	`board`, a 2D integer matrix
Output	The stable board after repeated crushing
Candy	Positive integer
Empty cell	`0`
Crush rule	Three or more equal candies in a row or column
Gravity rule	Candies fall straight down
Repeat rule	Continue until no crushable group remains

The function shape is:

class Solution:
    def candyCrush(self, board: list[list[int]]) -> list[list[int]]:
        ...

Examples

Example:

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],
]

Output:

[
    [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],
]

The important point is that crushes happen simultaneously. We cannot remove one group immediately and then search for the next group using the partially modified board.

First Thought: Remove Matches Immediately

A simple approach is to scan the board and remove a group as soon as we find it.

This is wrong because multiple groups in the same round must be crushed at the same time.

For example, a candy can belong to both a horizontal group and a vertical group. If we remove the horizontal group immediately, we may destroy information needed to detect the vertical group.

So we need two phases:

Mark all candies that should be crushed.
Crush them all together.

Key Insight

Use negative values as temporary marks.

If a candy should be crushed, change:

board[r][c]

to:

-abs(board[r][c])

This marks the cell while preserving the candy type.

Why this works:

Need	How negative marking helps
Know cell should be crushed	Negative value means marked
Still compare candy type	Use `abs(board[r][c])`
Keep empty cells separate	`0` remains `0`
Crush simultaneously	Only set marked cells to `0` after all marks are done

After marking, apply gravity column by column.

Algorithm

Repeat until stable:

Set changed = False.
Scan all horizontal triples:
- If three consecutive candies have the same nonzero absolute value, mark them negative.
Scan all vertical triples:
- If three consecutive candies have the same nonzero absolute value, mark them negative.
If no candy was marked, return the board.
For each column:
- Move positive candies downward.
- Fill remaining top cells with 0.
Repeat.

Correctness

The marking phase checks every possible horizontal and vertical run of length at least three. If a run is crushable, then every triple inside that run causes its cells to be marked. Therefore all candies in every crushable run are marked.

Using absolute values ensures that already marked candies still participate in detecting other crushable groups in the same round. This is necessary for simultaneous crushing.

After marking finishes, every marked cell is exactly a candy that must be crushed in the current round. The gravity phase removes those marked cells by ignoring negative values and compacts all positive candies downward in each column. This preserves the vertical order of surviving candies and fills all empty cells above them with 0.

Each round therefore exactly simulates one Candy Crush step. The algorithm repeats until a round finds no crushable group. At that point the board is stable, so returning it is correct.

Complexity

Let:

m = number of rows
n = number of columns

Metric	Value	Why
Time per round	`O(mn)`	Scan rows, scan columns, then apply gravity
Space	`O(1)` extra	Marking is done in-place

There may be multiple rounds, but each round removes at least one candy if it continues. With board size at most 50 x 50, direct simulation is acceptable.

Implementation

class Solution:
    def candyCrush(self, board: list[list[int]]) -> list[list[int]]:
        rows = len(board)
        cols = len(board[0])

        while True:
            changed = False

            for r in range(rows):
                for c in range(cols - 2):
                    value = abs(board[r][c])

                    if (
                        value != 0
                        and abs(board[r][c + 1]) == value
                        and abs(board[r][c + 2]) == value
                    ):
                        board[r][c] = -value
                        board[r][c + 1] = -value
                        board[r][c + 2] = -value
                        changed = True

            for r in range(rows - 2):
                for c in range(cols):
                    value = abs(board[r][c])

                    if (
                        value != 0
                        and abs(board[r + 1][c]) == value
                        and abs(board[r + 2][c]) == value
                    ):
                        board[r][c] = -value
                        board[r + 1][c] = -value
                        board[r + 2][c] = -value
                        changed = True

            if not changed:
                return board

            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

                for r in range(write, -1, -1):
                    board[r][c] = 0

Code Explanation

The outer loop repeats until the board is stable:

while True:
    changed = False

Horizontal triples are detected by checking three adjacent cells:

value = abs(board[r][c])

We use abs because a candy may already be marked from another match in the same round.

If three candies match, mark them negative:

board[r][c] = -value
board[r][c + 1] = -value
board[r][c + 2] = -value

The vertical scan uses the same idea, but across rows:

abs(board[r + 1][c]) == value
abs(board[r + 2][c]) == value

If no cell was marked, the board has no crushable group:

if not changed:
    return board

Gravity is applied one column at a time.

The write pointer shows where the next surviving candy should fall:

write = rows - 1

Scan upward. Keep only positive candies:

if board[r][c] > 0:
    board[write][c] = board[r][c]
    write -= 1

Finally, fill the remaining top cells with zero:

for r in range(write, -1, -1):
    board[r][c] = 0

Example Walkthrough

Suppose one row contains:

[1, 1, 1, 2]

The horizontal scan marks the three 1s:

[-1, -1, -1, 2]

After gravity and clearing, if this is a single row, it becomes:

[0, 0, 0, 2]

For a column:

[
    [4],
    [0],
    [5],
    [6],
]

gravity compacts positive candies downward:

[
    [0],
    [4],
    [5],
    [6],
]

Testing

def test_candy_crush():
    s = Solution()

    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],
    ]

    expected = [
        [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],
    ]

    assert s.candyCrush(board) == expected

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

    assert s.candyCrush(board) == [
        [0, 0, 0],
        [2, 3, 4],
        [5, 6, 7],
    ]

    board = [
        [1, 2, 3],
        [1, 5, 6],
        [1, 8, 9],
    ]

    assert s.candyCrush(board) == [
        [0, 2, 3],
        [0, 5, 6],
        [0, 8, 9],
    ]

    board = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]

    assert s.candyCrush(board) == [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]

    print("all tests passed")

test_candy_crush()

Test coverage:

Test	Why
Official-style large board	Confirms repeated crushing and gravity
Horizontal triple	Confirms row marking
Vertical triple	Confirms column marking
Already stable board	Confirms no unnecessary changes