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.