LC: 723. Candy Crush - spiralgo/algorithms GitHub Wiki

723. Candy Crush:

The Essence:

From the problem statement:

After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps

From this, we can recognize that we need to continually check the board until no "crushing" can be done. When more than 3 candies are next to each other, instead of trying to look for all of them, looking only for a window of 3 suffices. If other windows of 3 appear, the new candy tiles can also be marked to be crushed.

Details:

If a board is stable, it's certain that no candies will be crushed. An extra true/false flag can be used for this. When 3 same candies in a column or row window are detected, instead of editing the original board, we can edit some copied board. With this, if another window of candies as the continuation of this exists, then we would be able to detect them too. For the dropping of candies, the index of the highest candy in a column before a 0 can be stored. Dropping this would decrement the index to look for the candy below it.