cswork / libraryOpen practice workspace

Coding questions · Uber

Perform matrix Candy Crush elimination

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.

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.

Perform matrix Candy Crush elimination

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.

Hints

  1. 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.
  2. A cell qualifies for removal when it has >= 2 (not exactly 2) orthogonal neighbors of the same non-zero color.
  3. 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.