LeetCode 723 - Candy Crush

LeetCode Problem 723

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Matrix, Simulation

Solution

Problem Understanding

This problem is essentially a simulation of the Candy Crush game, where we need to repeatedly crush candies in a grid until the board reaches a stable state. The input is an m x n matrix of integers representing different types of candies, and 0 represents empty cells. Each integer from 1 to 2000 represents a distinct candy type. The rules are that if three or more candies of the same type are aligned consecutively in a row or a column, they "crush" and disappear, leaving empty cells. After candies crush, any candy above an empty cell falls down until it reaches another candy or the bottom of the board. This process repeats until no further candies can be crushed.

The expected output is the final stable board after all possible crushing and falling actions. Constraints indicate that the board size is at most 50x50, which is small enough for a straightforward simulation approach to be feasible. Edge cases include boards that are already stable, boards with multiple overlapping crushes, and cases where new crushes are triggered after falling candies.

Approaches

The brute-force approach would be to iterate through the board, detect all crushable sequences (horizontal and vertical), mark them, then crush them and let candies fall. Repeat this process until no more candies can be crushed. While correct, this approach may repeatedly scan the entire board, making it less efficient. Each full scan could take O(mn) and repeated scans could lead to higher overall runtime.

The optimal approach leverages a systematic marking and dropping strategy. Instead of using complex data structures, we mark candies to crush using negative values or a separate boolean board, then crush all marked candies in one pass. For falling candies, we process each column independently using a "write pointer" from the bottom, moving candies down efficiently. We repeat the process until no crushes occur. This reduces unnecessary repeated iterations over non-crushable areas and makes the solution straightforward and efficient.

Algorithm Walkthrough

1. Initialize a flag found to indicate whether any candies are crushed in the current iteration. Set it to True to start the loop.

2. While found is True, do the following:

3. Set found to False. Iterate over the board to identify horizontal and vertical sequences of three or more identical candies. Mark these positions for crushing, either by using a negative value or a separate boolean marker. If any sequence is found, set found to True.

4. After marking, iterate over the board again and crush all marked candies by setting them to 0.

5. Process each column independently to drop candies. Start from the bottom of each column with a "write pointer". For each non-zero candy encountered from bottom to top, move it to the write position and decrement write. After moving all candies, fill remaining positions above write with 0.

6. Repeat the above loop until no new crushes are found (found remains False).

Why it works: The loop invariant is that after each iteration, all crushable candies are crushed and all remaining candies are in the lowest possible positions. By repeatedly applying these steps, we ensure no new crushable sequences remain, guaranteeing stability.

Python Solution

from typing import List

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])
        found = True
        
        while found:
            found = False
            crush = [[False]*n for _ in range(m)]
            
            # Mark horizontal crushes
            for i in range(m):
                for j in range(n-2):
                    if board[i][j] != 0 and board[i][j] == board[i][j+1] == board[i][j+2]:
                        crush[i][j] = crush[i][j+1] = crush[i][j+2] = True
                        found = True
            
            # Mark vertical crushes
            for i in range(m-2):
                for j in range(n):
                    if board[i][j] != 0 and board[i][j] == board[i+1][j] == board[i+2][j]:
                        crush[i][j] = crush[i+1][j] = crush[i+2][j] = True
                        found = True
                        
            # Crush candies
            for i in range(m):
                for j in range(n):
                    if crush[i][j]:
                        board[i][j] = 0
            
            # Drop candies
            for j in range(n):
                write = m - 1
                for i in range(m-1, -1, -1):
                    if board[i][j] != 0:
                        board[write][j] = board[i][j]
                        write -= 1
                for i in range(write, -1, -1):
                    board[i][j] = 0
                    
        return board

The Python implementation closely follows the algorithm. Horizontal and vertical crushes are marked separately, and a crush matrix avoids in-place conflicts. Dropping is handled efficiently with a bottom-up write pointer per column.

Go Solution

func candyCrush(board [][]int) [][]int {
    m, n := len(board), len(board[0])
    found := true

    for found {
        found = false
        crush := make([][]bool, m)
        for i := range crush {
            crush[i] = make([]bool, n)
        }

        // Horizontal crush
        for i := 0; i < m; i++ {
            for j := 0; j < n-2; j++ {
                if board[i][j] != 0 && board[i][j] == board[i][j+1] && board[i][j] == board[i][j+2] {
                    crush[i][j], crush[i][j+1], crush[i][j+2] = true, true, true
                    found = true
                }
            }
        }

        // Vertical crush
        for i := 0; i < m-2; i++ {
            for j := 0; j < n; j++ {
                if board[i][j] != 0 && board[i][j] == board[i+1][j] && board[i][j] == board[i+2][j] {
                    crush[i][j], crush[i+1][j], crush[i+2][j] = true, true, true
                    found = true
                }
            }
        }

        // Crush candies
        for i := 0; i < m; i++ {
            for j := 0; j < n; j++ {
                if crush[i][j] {
                    board[i][j] = 0
                }
            }
        }

        // Drop candies
        for j := 0; j < n; j++ {
            write := m - 1
            for i := m - 1; i >= 0; i-- {
                if board[i][j] != 0 {
                    board[write][j] = board[i][j]
                    write--
                }
            }
            for i := write; i >= 0; i-- {
                board[i][j] = 0
            }
        }
    }

    return board
}

In Go, slices are used to represent the board and the crush markers. The approach mirrors Python, with explicit initialization of 2D boolean slices. The same logic applies, handling edge cases and repeated crushing naturally.

Worked Examples

Example 1:

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

First iteration: detect crushes in last row (three 2s horizontally). Set crush flags. Drop candies above, resulting in intermediate board with 0s. Repeat the loop until no crushable candies remain. Final stable board:

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

Example 2:

Input: [[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]]

Detect horizontal crushes at positions [0,2],[0,3],[0,4] etc.,