{x}
blog image

Candy Crush

723. Candy Crush

Description

This problem simulates the Candy Crush game's elimination process. Given a grid of candies represented by an integer matrix board, where board[i][j] is the candy type, and 0 represents an empty cell, we need to repeatedly crush candies and let them drop until the board stabilizes. The rules are:

  1. Crushing: If three or more candies of the same type are adjacent horizontally or vertically, they are crushed and become empty (0).
  2. Dropping: After crushing, candies above empty cells drop down to fill the empty spaces.
  3. Iteration: Steps 1 and 2 are repeated until no more candies can be crushed.

The final stabilized board needs to be returned.

Solution: Simulation

The solution uses a simulation approach. It iteratively crushes candies and drops them until the board reaches a stable state. The core logic involves these steps:

  1. Crushing Candies: The code iterates through the board, checking for horizontal and vertical groups of three or more identical candies. If found, these candies are marked as negative to indicate they should be removed. The run boolean variable tracks whether any candies were crushed in the current iteration.

  2. Dropping Candies: After crushing, the board needs to be updated to reflect the candies dropping down. For each column, the code iterates from bottom to top. Positive values (candies) are moved to the bottom, and the remaining top cells are set to 0.

  3. Iteration: The while run loop continues until no candies are crushed in an iteration (run becomes false).

Time Complexity: O(m²n²), where 'm' is the number of rows and 'n' is the number of columns. In the worst case, the crushing and dropping steps might need to be repeated many times. While each individual step is O(mn), the nested loop structure makes it potentially quadratic in the worst case scenario where many crushing actions are needed.

Space Complexity: O(1). The algorithm modifies the board in place, so the space used is constant.

Code (Python3, Java, C++, Go, TypeScript)

The code implementations across different languages follow the same general logic:

Python3:

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])
        run = True
        while run:
            run = False
            # Crush horizontally
            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]):
                        run = True
                        board[i][j] = board[i][j - 1] = board[i][j - 2] = -abs(board[i][j])
            # Crush vertically
            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]):
                        run = True
                        board[i][j] = board[i - 1][j] = board[i - 2][j] = -abs(board[i][j])
            # Drop candies
            if run:
                for j in range(n):
                    k = m - 1
                    for i in range(m - 1, -1, -1):
                        if board[i][j] > 0:
                            board[k][j] = board[i][j]
                            k -= 1
                    while k >= 0:
                        board[k][j] = 0
                        k -= 1
        return board

Java:

class Solution {
    public int[][] candyCrush(int[][] board) {
        int m = board.length, n = board[0].length;
        boolean run = true;
        while (run) {
            run = false;
            //Crush horizontally and vertically (similar logic to Python)
            // ... (Java code for crushing similar to Python) ...
            // Drop candies (similar logic to Python)
            // ... (Java code for dropping similar to Python) ...
        }
        return board;
    }
}

C++:

class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        bool run = true;
        while (run) {
            run = false;
            //Crush horizontally and vertically (similar logic to Python)
            // ... (C++ code for crushing similar to Python) ...
            // Drop candies (similar logic to Python)
            // ... (C++ code for dropping similar to Python) ...
        }
        return board;
    }
};

Go:

func candyCrush(board [][]int) [][]int {
	m := len(board)
	n := len(board[0])
	run := true
	for run {
		run = false
		//Crush horizontally and vertically (similar logic to Python)
        // ... (Go code for crushing similar to Python) ...
		// Drop candies (similar logic to Python)
        // ... (Go code for dropping similar to Python) ...
	}
	return board
}
 
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript:

function candyCrush(board: number[][]): number[][] {
    const m = board.length;
    const n = board[0].length;
    let run = true;
    while (run) {
        run = false;
        //Crush horizontally and vertically (similar logic to Python)
        // ... (TypeScript code for crushing similar to Python) ...
        // Drop candies (similar logic to Python)
        // ... (TypeScript code for dropping similar to Python) ...
    }
    return board;
}

(Note: The Java, C++, Go, and TypeScript code snippets would contain the same core logic as the Python code, just adapted to the syntax of those languages. The crushing and dropping parts are omitted for brevity, but they directly mirror the Python implementation.)

This detailed explanation and the provided code snippets across multiple languages illustrate the simulation approach to solving the Candy Crush problem. Remember that the crucial parts are the iterative crushing and dropping until the board stabilizes.