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.

Simulate one-round color elimination on a grid

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an m x n integer matrix board where board[r][c] > 0 represents a color and 0 represents empty: ( 1) A nonzero cell at (r,c) explodes in this round if at least two of its four orthogonal neighbors (up, down, left, right), within bounds, have the same color value as board[r][c]. ( 2) Determine all exploding cells simultaneously based on the initial board for this round; set them to 0. ( 3) Then apply gravity: in each column, slide all nonzero values down to the bottom, preserving their relative order, and fill the remaining cells at the top with 0s. Return the matrix after exactly one such round (detect explosions once, remove, then gravity). Implement the function and analyze time and space complexity.

Quick Answer: This question evaluates array and matrix manipulation skills, including grid traversal, orthogonal neighbor-checking, simultaneous state-update detection, and maintaining relative order while applying gravity-like column operations.

You are given an m x n integer matrix `board` where `board[r][c] > 0` represents a color and `0` represents an empty cell. Simulate exactly one round of color elimination: 1. Detect explosions: A nonzero cell at (r, c) explodes in this round if at least two of its four orthogonal neighbors (up, down, left, right) that lie within the bounds of the board have the same color value as `board[r][c]`. 2. Eliminate simultaneously: Determine ALL exploding cells based on the INITIAL board for this round (do not let one removal affect another cell's neighbor count), then set every exploding cell to `0`. 3. Apply gravity: In each column independently, slide all remaining nonzero values down to the bottom while preserving their relative order, and fill the now-vacant cells at the top of the column with `0`. Return the matrix after exactly one such round. Detection happens once on the original board, then removal, then a single gravity pass. Example: Input: [[1,1,1],[0,1,0],[2,2,0]] Only cell (0,1) has >= 2 same-color neighbors, so it explodes. After removal the board is [[1,0,1],[0,1,0],[2,2,0]]; after gravity per column the result is [[0,0,0],[1,1,0],[2,2,1]].

Constraints

1 <= m, n (the board may also be empty, in which case return it unchanged)
0 <= board[r][c]; a value of 0 means empty, any positive value is a color
Explosion detection uses the ORIGINAL board for the whole round (simultaneous removal)
A cell explodes only if at least two in-bounds orthogonal neighbors share its color

Examples

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

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

Explanation: Only (0,1) has >=2 same-color (1) neighbors and explodes. Board becomes [[1,0,1],[0,1,0],[2,2,0]]; after per-column gravity the survivors fall to give [[0,0,0],[1,1,0],[2,2,1]].

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)

Expected Output: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Explanation: All colors are distinct, so no cell has even one same-color neighbor. Nothing explodes and gravity changes nothing.

Input: ([[5]],)

Expected Output: [[5]]

Explanation: A single cell has no neighbors, so it cannot explode.

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

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

Explanation: Every cell has exactly two same-color orthogonal neighbors, so all four explode; the board is emptied.

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

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

Explanation: In each side column only the middle cell has two vertical same-color neighbors, so (1,0) and (1,2) explode. Survivors fall, leaving two 1s at the bottom of each side column.

Input: ([],)

Expected Output: []

Explanation: Empty board edge case: returned unchanged.

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

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

Explanation: Single row: the two inner cells each have two same-color horizontal neighbors and explode; the two end cells have only one neighbor and survive. Gravity does nothing in a one-row board.

Hints

Detect all explosions FIRST against the original board (e.g. into a separate boolean grid), then remove — otherwise an early removal would wrongly change a later cell's neighbor count within the same round.
A cell at (r,c) explodes when >= 2 of its up/down/left/right in-bounds neighbors equal board[r][c]. Diagonals do not count.
Gravity is per column: collect the nonzero values top-to-bottom, then place them at the BOTTOM of the column preserving order, filling the top with zeros.

Quick Overview

This question evaluates array and matrix manipulation skills, including grid traversal, orthogonal neighbor-checking, simultaneous state-update detection, and maintaining relative order while applying gravity-like column operations.