Perform matrix Candy Crush elimination
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Implement a function that, given an m × n integer matrix representing colored blocks (same integers = same color), performs one round of "Candy-Crush" elimination:
A cell is removed (set to
0) if at least two of its four neighbors (up, down, left, right) share the same color as the cell.
After removals, all remaining non-zero cells in each column fall down to fill empty spaces; zeros rise to the top.
Return the resulting matrix after this single round.
Quick Answer: This question evaluates a candidate's competency in matrix and grid manipulation, neighborhood/adjacency checks, and simulation of state transitions in an array-based board.
You are given an `m x n` integer matrix `matrix` representing a grid of colored blocks. Equal integers represent the same color; `0` represents an empty cell.
Perform exactly **one** round of "Candy Crush" elimination, in two phases:
1. **Mark & remove.** A non-zero cell is removed (set to `0`) if **at least two** of its four orthogonal neighbors (up, down, left, right) share the same color (same integer) as the cell. All removals are decided **simultaneously** based on the original matrix — a cell that gets removed still counts toward its neighbors' removal decisions in this same round.
2. **Gravity.** After all removals, every remaining non-zero cell in each column falls straight down to fill empty spaces; the zeros rise to the top of that column. Relative order of the surviving cells within a column is preserved.
Return the resulting matrix after this single round. Do **not** repeat the process — only one round is performed.
**Example**
```
Input: [[1, 1, 1],
[1, 2, 2],
[3, 4, 5]]
Output: [[0, 0, 1],
[1, 2, 2],
[3, 4, 5]]
```
The three top-left 1's form an L-shape: (0,0) has two same-color neighbors (right and down), and (0,1) has two (left and right), so both are removed. (0,2) and (1,0) each have only one same-color neighbor, so they survive. After removal column 0 is `[0,1,3]` and column 1 is `[0,2,4]`; gravity leaves them unchanged since the only empties are already on top.
Constraints
- 1 <= m, n (the matrix may also be empty, in which case return it unchanged)
- 0 <= matrix[i][j], where 0 denotes an empty cell
- Removals are decided simultaneously from the original matrix (mark first, then clear).
- Only ONE round of elimination is performed; do not cascade.
- Within each column, surviving cells keep their top-to-bottom relative order after gravity.
Examples
Input: ([[1, 1, 1], [1, 2, 2], [3, 4, 5]],)
Expected Output: [[0, 0, 1], [1, 2, 2], [3, 4, 5]]
Explanation: (0,0) [right+down] and (0,1) [left+right] each have two same-color (1) neighbors and are removed; (0,2) and (1,0) have only one, so they survive. Gravity leaves the columns unchanged (empties already on top).
Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Expected Output: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Explanation: All cells are distinct colors, so no cell has even one same-color neighbor; nothing is removed and the matrix is returned unchanged.
Hints
- Compute all removals first into a separate boolean grid, scanning the ORIGINAL matrix; only after the full scan should you zero out the marked cells. Mutating in place mid-scan changes a neighbor's color and corrupts later decisions.
- A cell qualifies for removal when it has >= 2 (not exactly 2) orthogonal neighbors of the same non-zero color.
- For gravity, process each column independently: collect its non-zero values top-to-bottom, then write them back at the BOTTOM of the column and fill the top with zeros.