723. Candy Crush - Detailed Explanation

Problem Statement:

You are given an m x n integer grid board representing the state of a Candy Crush game. Each element in the grid is either:

• A positive integer, representing different types of candies, or
• 0, representing an empty cell.

Your goal is to repeatedly "crush" candies until no more candies can be crushed. Candy crushing follows these rules:

1. Crushing Rule:
   If three or more candies of the same type are adjacent either horizontally or vertically, they are considered “crushable.”

2. Crushing Process:

   • When candies are crushable, mark them (so that you know they must be set to 0).
   • All marked candies are simultaneously crushed (i.e., set to 0).

3. Gravity:
   After the candies are crushed, any candy that is above an empty cell (a cell with 0) will fall down to fill the empty space. New empty cells are created at the top of the column.

4. Repeat:
   Continue the process (crush then gravity) until no more candies can be crushed. Return the final board.

Note: The board is guaranteed to become stable after a finite number of crushes.

Example Inputs and Outputs:

1. Example 1:

   Input:

   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:
   The final stable board after applying all crushes and gravity moves. (The exact output is a transformed board after several iterations of crush and gravity. For brevity, the sample output is not written here—but you can follow the simulation to see how candies are crushed and then fall.)

2. Example 2 (Smaller Board):

   Input:

   board = [
     [1, 1, 1],
     [2, 3, 2],
     [2, 3, 3]
   ]
   

   Intermediate Step:

   • The first row has three adjacent 1s, so they are crushable.

   After Crush:

   board = [
     [0, 0, 0],
     [2, 3, 2],
     [2, 3, 3]
   ]
   

   After Gravity:
   The above board remains the same because there is no candy above a zero (in this small example, gravity might not change much).

   Output:
   The board after all possible crushes are performed (in this simple case, it may become stable after one crush).

Hints for Solving the Problem:

1. Detecting Crushable Candies:

   • How can you check every cell to see if it is part of a horizontal or vertical sequence of three or more identical, nonzero candies?
   • Consider iterating through the board and marking candies that are crushable without interfering with your detection of others.

2. Marking Strategy:

   • One effective approach is to mark crushable candies by using a negative sign (or any special marker) to indicate that these candies will be crushed, so you don’t lose their identity while scanning.

3. Applying Gravity:

   • Once candies are crushed (set to zero), how do you make the remaining candies "fall" to fill the empty spaces?
   • Process each column separately from bottom to top, moving non-zero candies downwards and filling the top with zeros.

4. Repeat Until Stable:

   • How do you know when to stop the simulation?
   • Continue the process until no candies are marked for crushing in an entire pass over the board.

Approach 1: Simulation with Repeated Scans (Brute Force Simulation)

Step-by-Step Explanation:

1. Marking Phase:

   • Traverse the board and for every candy (nonzero value), check:
     • Horizontally: If there exist two adjacent cells to the right that have the same absolute value.
     • Vertically: If there exist two adjacent cells below that have the same absolute value.
   • If found, mark all those cells (e.g., by making the value negative).

2. Crush Phase:

   • Once the entire board is scanned and candies are marked, traverse the board again and set any marked candy (negative value) to 0.

3. Gravity Phase:

   • For each column, iterate from the bottom up using a write pointer:
     • Write nonzero values to the bottom of the column.
     • After all nonzero values are moved, fill the remaining cells (at the top) with zeros.

4. Repeat:

   • Repeat the marking, crushing, and gravity phases until no new candies can be crushed (i.e., no cell was marked during the marking phase).

Brute Force Simulation Code in Python