Problem Description

This problem asks you to implement the basic elimination mechanism from the game Candy Crush on a 2D grid.

You're given an m x n integer array board where each board[i][j] represents a type of candy (positive integers), and 0 represents an empty cell. Your task is to simulate the candy crushing process until the board reaches a stable state.

The crushing rules work as follows:

1. Identify crushable candies: Find any group of three or more candies of the same type that are adjacent either horizontally or vertically. All such groups should be marked for crushing simultaneously.

2. Crush the candies: Remove all marked candies at once by making those positions empty (setting them to 0).

3. Apply gravity: After crushing, candies above empty spaces should fall down to fill the gaps. Candies drop straight down until they hit another candy or reach the bottom of the board. Multiple candies can fall simultaneously.

4. Repeat until stable: After candies drop, new crushing opportunities may appear. Keep repeating steps 1-3 until no more candies can be crushed.

The solution uses a clever marking technique - instead of immediately removing candies, it marks them with negative values first. This allows the algorithm to identify all crushable groups in one pass before actually removing them. The gravity simulation is implemented by using a two-pointer approach to shift non-empty candies downward in each column.

For example, if you have a row like [1, 1, 1, 2], the three consecutive 1s would be crushed, leaving [0, 0, 0, 2] after applying gravity. The process continues until no more groups of three or more identical candies exist in any row or column.

Intuition

The key insight is that we need to simulate the actual Candy Crush game mechanics, which involves repeatedly finding matches and applying gravity until no more moves are possible.

The first challenge is how to handle simultaneous crushing. If we immediately remove candies as we find them, we might miss overlapping groups. For instance, if we have a cross pattern where both a horizontal and vertical group of three share a candy, we need to crush all of them together. The clever trick here is to use negative numbers as markers. When we find a group of three or more matching candies, instead of removing them immediately, we mark them by making their values negative. This preserves the candy type information (through abs()) while flagging them for removal.

Why negative numbers? Because:

• They're distinguishable from positive candy values
• We can still identify the candy type using abs()
• Empty cells (0) remain unaffected
• We can check multiple patterns without losing information

The second insight is about the order of operations. We first scan horizontally across all rows, then vertically down all columns. This ensures we catch all possible matches in a single iteration. We check for patterns of three consecutive candies by comparing board[i][j], board[i][j-1], and board[i][j-2] for horizontal matches (and similar for vertical).

For the gravity simulation, we use a two-pointer technique for each column. Starting from the bottom of each column, we maintain a write pointer k that tracks where the next non-crushed candy should be placed. As we scan upward, whenever we find a positive value (non-crushed candy), we move it to position k and decrement k. After processing all candies, any remaining positions above k are filled with zeros.

The overall flow becomes: mark crushable candies → apply gravity → check if anything was crushed → repeat if necessary. The run flag tracks whether any crushing occurred in the current iteration, determining whether we need another round.

Learn more about Two Pointers patterns.

Solution Approach

The implementation uses a simulation approach with a marking and dropping mechanism. Let's walk through the key components:

Main Loop Structure: The solution uses a while loop controlled by a run flag that continues until the board reaches a stable state (no more candies can be crushed).

Step 1: Mark Candies for Crushing

First, we scan horizontally across each row:

for i in range(m):
    for j in range(2, n):
        if board[i][j] and abs(board[i][j]) == abs(board[i][j-1]) == abs(board[i][j-2]):

• Start from column index 2 since we need to check three consecutive elements
• Check if current position is non-empty (board[i][j]) and matches the two positions to its left
• Use abs() to handle both positive values and previously marked negative values

When a match is found, mark all three positions as negative:

board[i][j] = board[i][j-1] = board[i][j-2] = -abs(board[i][j])

Then scan vertically down each column using similar logic:

for j in range(n):
    for i in range(2, m):
        if board[i][j] and abs(board[i][j]) == abs(board[i-1][j]) == abs(board[i-2][j]):

Step 2: Apply Gravity (Drop Candies)

If any candies were marked (run = True), process each column to drop candies:

for j in range(n):
    k = m - 1  # Write pointer starting from bottom
    for i in range(m - 1, -1, -1):  # Scan from bottom to top
        if board[i][j] > 0:  # Found a non-crushed candy
            board[k][j] = board[i][j]
            k -= 1

The two-pointer technique works as follows:

• k represents where the next candy should be placed (starting from the bottom)
• i scans upward looking for positive values (non-crushed candies)
• When found, place the candy at position k and move k up
• After processing all candies, fill remaining positions with zeros:

while k >= 0:
    board[k][j] = 0
    k -= 1

Step 3: Check for Stability

The run flag determines if another iteration is needed:

• Initially set to False at the start of each iteration
• Set to True whenever candies are marked for crushing
• If it remains False after scanning, the board is stable

Time Complexity: O(m * n * k) where k is the number of iterations needed to stabilize the board. In the worst case, k could be O(max(m, n)).

Space Complexity: O(1) as we modify the board in-place without using additional data structures.

The elegance of this solution lies in using negative marking to handle simultaneous crushing and the efficient two-pointer technique for simulating gravity, avoiding the need for temporary arrays or complex data structures.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Initial Board:

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

Iteration 1 - Marking Phase:

First, scan horizontally (checking groups of 3+ in rows):

• Row 0: No matches
• Row 1: No matches
• Row 2: No matches
• Row 3: No matches
• Row 4: No matches

Then, scan vertically (checking groups of 3+ in columns):

• Column 0: No matches
• Column 1: positions [1,1], [2,1], [3,1], [4,1] all have value 4 → Mark as -4
• Column 2: positions [2,2], [3,2], [4,2] all have value 4 → Mark as -4
• Column 3: positions [0,3], [1,3], [2,3], [3,3] have different values (5,3,5,5) - no consecutive match of 3
• Column 4: No matches

After marking:

[1, 3, 5, 5, 2]
[3,-4, 3, 3, 1]
[3,-4,-4, 5, 2]
[2,-4,-4, 5, 5]
[1,-4,-4, 1, 1]

Iteration 1 - Gravity Phase:

Process each column from bottom to top, moving positive values down:

Column 0: [1,3,3,2,1] → No changes needed (no negatives)

Column 1: [3,-4,-4,-4,-4]

• k=4 (start at bottom)
• i=4: board[4][1]=-4 (skip)
• i=3: board[3][1]=-4 (skip)
• i=2: board[2][1]=-4 (skip)
• i=1: board[1][1]=-4 (skip)
• i=0: board[0][1]=3 (positive!) → board[4][1]=3, k=3
• Fill remaining: board[3][1]=0, board[2][1]=0, board[1][1]=0, board[0][1]=0

Column 2: [5,3,-4,-4,-4]

• k=4, process similarly
• Result: [0,0,5,3,4] (the 4 at bottom came from board[0][2]=5, wait that's wrong...)

Let me recalculate Column 2: [5,3,-4,-4,-4]

• k=4 (start at bottom)
• i=4: board[4][2]=-4 (skip)
• i=3: board[3][2]=-4 (skip)
• i=2: board[2][2]=-4 (skip)
• i=1: board[1][2]=3 (positive!) → board[4][2]=3, k=3
• i=0: board[0][2]=5 (positive!) → board[3][2]=5, k=2
• Fill remaining: board[2][2]=0, board[1][2]=0, board[0][2]=0

After gravity:

[0, 0, 0, 5, 2]
[0, 0, 0, 3, 1]
[1, 0, 0, 5, 2]
[3, 0, 5, 5, 5]
[3, 3, 3, 1, 1]

Iteration 2 - Marking Phase:

Scan horizontally:

• Row 3: positions [3,2], [3,3], [3,4] all have value 5 → Mark as -5
• Row 4: positions [4,0], [4,1], [4,2] all have value 3 → Mark as -3

Scan vertically:

• Column 3: positions [2,3], [3,3] have value 5, but [3,3] is already -5
• Column 4: No new matches

After marking:

[0, 0, 0, 5, 2]
[0, 0, 0, 3, 1]
[1, 0, 0,-5, 2]
[3, 0,-5,-5,-5]
[-3,-3,-3, 1, 1]

Iteration 2 - Gravity Phase:

After applying gravity to each column:

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 2]
[0, 0, 0, 5, 1]
[1, 0, 0, 3, 2]
[3, 0, 0, 1, 1]

Iteration 3 - Marking Phase:

No groups of 3+ found horizontally or vertically. The run flag stays False.

Final stable board:

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 2]
[0, 0, 0, 5, 1]
[1, 0, 0, 3, 2]
[3, 0, 0, 1, 1]

The process demonstrates how:

1. Negative marking preserves candy type while flagging for removal
2. Gravity drops all candies simultaneously in each column
3. The process repeats until no more matches exist

Solution Implementation

Time and Space Complexity

Time Complexity: O(m² × n²)

The algorithm uses a while loop that continues until no more candies can be crushed. In the worst case, we might need to perform O(m × n) iterations (crushing one candy at a time in a cascading manner). Within each iteration:

• We scan the entire board twice to mark candies for crushing: O(m × n)
• We drop candies in each column: O(m × n)

Therefore, the overall time complexity is O(m × n) × O(m × n) = O(m² × n²), where m is the number of rows and n is the number of columns of the board.

Space Complexity: O(1)

The algorithm modifies the board in-place without using any additional data structures that scale with the input size. We only use a few constant variables (run, i, j, k) regardless of the board dimensions, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Using Absolute Values When Checking Matches

One of the most common mistakes is forgetting to use abs() when comparing candy values during the matching phase. This is crucial because candies that were marked for crushing in a previous part of the same iteration are represented as negative numbers.

Incorrect Code:

# This will miss matches involving already-marked candies
if board[i][j] == board[i][j-1] == board[i][j-2]:
    # Mark for crushing

Why it fails: If board[i][j-1] was already marked as -3 and board[i][j] and board[i][j-2] are 3, the comparison 3 == -3 == 3 returns False, missing a valid match.

Correct Code:

if board[i][j] and abs(board[i][j]) == abs(board[i][j-1]) == abs(board[i][j-2]):
    # Mark for crushing

2. Incorrect Gravity Implementation - Not Scanning from Bottom

Another frequent error is implementing the gravity drop incorrectly by scanning from top to bottom instead of bottom to top.

Incorrect Code:

for col in range(cols):
    write_row = 0
    for row in range(rows):  # Wrong direction!
        if board[row][col] > 0:
            board[write_row][col] = board[row][col]
            write_row += 1
    while write_row < rows:
        board[write_row][col] = 0
        write_row += 1

Why it fails: This places candies at the top of the board instead of letting them fall to the bottom, violating the gravity rule.

Correct Code:

for col in range(cols):
    write_row = rows - 1  # Start from bottom
    for row in range(rows - 1, -1, -1):  # Scan bottom to top
        if board[row][col] > 0:
            board[write_row][col] = board[row][col]
            write_row -= 1
    while write_row >= 0:
        board[write_row][col] = 0
        write_row -= 1

3. Crushing Candies Immediately Instead of Marking First

A subtle but critical mistake is crushing candies immediately when found instead of marking all crushable candies first.

Incorrect Approach:

# Wrong: Crushing immediately
for row in range(rows):
    for col in range(2, cols):
        if board[row][col] == board[row][col-1] == board[row][col-2]:
            board[row][col] = board[row][col-1] = board[row][col-2] = 0  # Immediate removal!

Why it fails: This can cause cascading issues where:

• A candy that's part of both a horizontal and vertical match might only be counted once
• The board state changes during scanning, potentially missing valid matches
• Example: In a T-shape or L-shape formation of identical candies, immediate removal would prevent detecting the perpendicular match

Correct Approach: Mark all matches with negative values first, then remove them all at once during the gravity phase. This ensures all valid matches are identified before any board modifications occur.