480. Candy Crush
You are given board, an m × n grid of integers modeling a candy-matching game. A positive value is a candy of that flavor; 0 is an empty cell.
The board settles by repeating one round until nothing changes:
- Crush. Find every cell that belongs to a horizontal or vertical run of three or more equal, non-zero values. All such cells are cleared simultaneously — mark first, then set every marked cell to
0at once. A cell can be part of a row run and a column run at the same time; it is still just cleared. - Fall. Gravity acts on each column independently: candies slide straight down into the empty cells below them, keeping their relative order, and the zeros end up stacked on top.
If a crush created new runs, the next round crushes those too — cascades keep going until the board is stable (no run of three or more exists anywhere).
Return the final, stable board as an m × n grid of integers.
Example 1:
Input: board = [[1,3,5,5],[2,3,3,5],[1,3,2,2],[2,2,2,4]]
Output: [[0,0,0,5],[1,0,5,5],[2,0,3,2],[1,0,2,4]]
Explanation: The column of 3s (rows 0–2, column 1) and the row of 2s (row 3, columns 0–2) crush together. Gravity then drops each column: column 0 becomes 1,2,1 stacked at the bottom, column 2 becomes 5,3,2 stacked at the bottom. No new run appears, so the board is stable after one round.
Example 2:
Input: board = [[3,1,2],[3,1,2],[3,3,3],[1,2,2]]
Output: [[0,0,0],[0,1,0],[0,1,0],[1,2,0]]
Explanation: Round 1 crushes the column of 3s and the row of 3s (they share the corner cell). After the fall, column 2 holds 2,2,2 stacked at the bottom — a brand-new vertical run — so round 2 crushes it. That cascade leaves the stable board.
Constraints:
- 1 ≤ m, n ≤ 50
- 0 ≤ board[r][c] ≤ 2000
- Runs only count horizontally or vertically, never diagonally, and only for non-zero values.
Hints:
Don't clear as you scan — a cell can belong to two runs at once, and clearing early destroys the second run before you've seen it. Mark everything first, then clear all marks in one sweep.
To find runs it's enough to check windows of exactly three: every run of length k >= 3 is covered by its overlapping 3-windows. Compare board[r][c], board[r][c+1], board[r][c+2] (and the vertical twin).
Gravity is a two-pointer write per column: walk from the bottom with a read pointer, copy every surviving candy down to a write pointer, then fill the rest of the column with zeros. Repeat crush+fall until a full crush pass marks nothing.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = [[1,3,5,5],[2,3,3,5],[1,3,2,2],[2,2,2,4]]
Expected output: [[0,0,0,5],[1,0,5,5],[2,0,3,2],[1,0,2,4]]