Candy Crush
Medium · Matrix · Array · Two Pointers · Matrix · Simulation
Problem
You are given an m x n integer grid board for a candy-crushing game. A positive value is a candy of that type and 0 is an empty cell. Make the board stable by repeating these steps:
- Find every run of three or more equal candies in a row or a column. Mark all of them at once (a candy can belong to a horizontal and a vertical run at the same time).
- Crush every marked candy at the same time: those cells become 0.
- Let gravity act: in each column, the candies above empty cells fall until they rest on another candy or the bottom. No new candies enter from the top.
- If step 1 found anything, go back to step 1; otherwise the board is stable.
Return the stable board.
Examples
Input: board = [[1,2,3],[4,2,5],[6,2,7],[1,1,3]] Output: [[1,0,3],[4,0,5],[6,0,7],[1,1,3]]
The three 2s in column 1 are crushed and nothing sits above them, so that column becomes 0, 0, 0, 1 and no new run forms.
Input: board = [[2,3,3],[4,1,1],[5,5,1],[3,3,3]] Output: [[0,0,0],[2,3,3],[4,1,1],[5,5,1]]
The bottom row of 3s is crushed, everything above drops one row, and the new board has no run.
Constraints
- m == len(board), n == len(board[i])
- 3 <= m, n <= 50
- 1 <= board[i][j] <= 2000 at the start
Approaches
- Measure every run, drop one row at a time — time O((m · n)² · (m + n) / 3), space O(m · n)
Follow-up
Each round rescans the whole board, though only the columns that moved can hold new runs. Can you limit the next scan to the cells that fell and their neighbors? Keep the set of moved cells and check only the windows of three that include one of them.
Related problems
Start free on Cariara · Coding problems · System design studio
