How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

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.

Input: ([[1, 1], [1, 1]],)

Expected Output: [[0, 0], [0, 0]]

Explanation: Every cell has exactly two same-color (1) neighbors, so the whole 2x2 block is removed; the board becomes all zeros.

Input: ([[5]],)

Expected Output: [[5]]

Explanation: A single cell has no neighbors, so it cannot be removed; the matrix is unchanged.

Input: ([],)

Expected Output: []

Explanation: Empty matrix edge case: nothing to process, returned as-is.

Input: ([[2, 2, 2, 2]],)

Expected Output: [[2, 0, 0, 2]]

Explanation: Single row, so only left/right neighbors count. The two middle 2's each have two same-color neighbors and are removed; the two end 2's have only one neighbor and survive. Gravity is a no-op for a single row.

Input: ([[3], [3], [3], [3]],)

Expected Output: [[0], [0], [3], [3]]

Explanation: Single column, so only up/down neighbors count. The two interior cells each have two same-color neighbors and are removed, leaving [3,0,0,3]; gravity drops the surviving 3's to the bottom -> [0,0,3,3].

Input: ([[1, 0, 1], [1, 0, 1], [1, 0, 1]],)

Expected Output: [[0, 0, 0], [1, 0, 1], [1, 0, 1]]

Explanation: The middle column is all zeros and is ignored. In each side column only the middle cell has two same-color neighbors (up and down) and is removed; after removal each side column is [1,0,1], and gravity drops the two 1's to the bottom -> [0,1,1].

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.

Quick Overview

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.