Practice/Meta/Leetcode 723. Candy Crush

Leetcode 723. Candy Crush

CodingMust

Problem

You are given an m × n integer grid where each cell contains a positive integer representing a colored tile. Your task is to simulate a tile-matching collapse mechanic:

1. Find matches: Identify all horizontal or vertical sequences of 3 or more consecutive identical values
2. Mark for removal: Mark all cells that are part of any match
3. Apply gravity: Remove marked cells (set to 0) and let remaining tiles fall down within their columns
4. Repeat: Continue this process until no more matches can be found

Return the final stable grid after all possible collapses have been performed.

Requirements

1. A match consists of 3 or more consecutive identical values in a row or column
2. If a cell is part of multiple matches (e.g., both horizontal and vertical), it should still be removed only once
3. After marking all matches in a single pass, remove them simultaneously before applying gravity
4. Gravity pulls tiles downward within each column, filling gaps left by removed tiles
5. Empty cells should be represented as 0 and appear at the top of each column
6. Continue the process until the grid reaches a stable state with no matches

Constraints

• 3 ≤ m, n ≤ 50
• 1 ≤ board[i][j] ≤ 2000
• You may modify the input board in-place
• Time complexity should be reasonable for the given constraints (simulation is acceptable)
• Space complexity should be O(m × n) or better

Examples

Example 1:

` Input: board = [[1,1,1],[2,2,3],[3,3,3]] Output: [[0,0,0],[0,0,0],[2,2,3]] Explanation:

• Row 0 contains three 1s (match)
• Row 2 contains three 3s (match)
• After removal and gravity, only the middle row remains at the bottom `

Example 2:

` Input: board = [[1,2,3],[1,2,4],[1,5,5]] Output: [[0,0,0],[0,0,0],[0,2,3]] Explanation:

• Pass 1: Column 0 has three 1s vertically → remove them
• After gravity: [[0,2,3],[0,2,4],[0,5,5]]
• Pass 2: Column 1 now has two 2s (not enough for match) but analyzing shows no new matches
• Actually, we need to reconsider: after first removal column 1 becomes [2,2,5] which is not a match
• Final state has only scattered values `

Example 3:

Input: board = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,2,3],[4,5,6],[7,8,9]] Explanation: No matches exist, so the board remains unchanged