Quick Overview

This question evaluates proficiency in 2D array manipulation, pattern detection for contiguous runs, and state simulation involving removal and gravity-like collapse of elements.

Detect runs and collapse a numeric grid

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an m x n grid of digits (0– 9). Phase 1: Find every horizontal or vertical run of length ≥ 3 consisting of the same digit. For each run, record [row, col, length], where [row, col] is the starting cell of the run (leftmost for horizontal runs, topmost for vertical runs). Return the list of runs sorted top-to-bottom and left-to-right (row ascending, then column ascending). Phase 2: Remove all cells that belong to any such run, let numbers above fall down within each column, and fill remaining empty cells with 0. Output the resulting grid after this operation.

Quick Answer: This question evaluates proficiency in 2D array manipulation, pattern detection for contiguous runs, and state simulation involving removal and gravity-like collapse of elements.

Part 1: Detect horizontal and vertical runs

You are given a rectangular grid of digits 0-9. A run is a maximal contiguous sequence of the same digit in a single row or a single column with length at least 3. Maximal means [7,7,7,7] is one run of length 4, not two runs of length 3. Return every run as [row, col, length, dir], where dir = 0 for a horizontal run and dir = 1 for a vertical run. [row, col] is the leftmost cell for a horizontal run or the topmost cell for a vertical run. Sort the runs by row ascending, then column ascending, then dir ascending. If the grid is empty, return [].

Constraints

  • 0 <= m, n <= 500
  • If the grid is non-empty, all rows have the same length n
  • 0 <= grid[r][c] <= 9

Examples

Input: ([[1,1,1,2],[3,4,4,4],[5,5,5,5]],)

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

Explanation: There are three horizontal maximal runs of length at least 3, and no vertical runs.

Input: ([[7,7,7],[7,1,2],[7,3,4]],)

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

Explanation: The top row forms a horizontal run of 7s, and the left column forms a vertical run of 7s.

Hints

  1. Scan each row once and each column once, counting the length of the current streak of equal values.
  2. Only add a run when a streak ends; that naturally gives you maximal runs and their starting positions.

Part 2: Remove run cells, apply gravity, and fill with 0

You are given an m x n grid of digits 0-9. First, find every cell that belongs to any horizontal or vertical maximal run of equal digits with length at least 3. Remove all such cells simultaneously. Then apply gravity independently in each column: the remaining numbers fall straight down, keeping their relative top-to-bottom order, and all empty cells at the top become 0. Return the grid after this single operation. Digits 0 in the input are treated like normal digits when detecting runs.

Constraints

  • 0 <= m, n <= 500
  • If the grid is non-empty, all rows have the same length n
  • 0 <= grid[r][c] <= 9
  • Perform exactly one detect-remove-collapse pass; do not repeat after gravity

Examples

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

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

Explanation: Row 0 has a horizontal run of three 1s. Column 1 has a vertical run of three 1s, and column 3 has a vertical run of three 2s. Remove all marked cells simultaneously, then let each column fall.

Input: ([[1,1,1],[1,5,6],[1,8,9]],)

Expected Output: [[0,0,0],[0,5,6],[0,8,9]]

Explanation: The top row is a horizontal run of three 1s, and the first column is also a vertical run of three 1s. After removal, only 5, 6, 8, and 9 remain and fall to the bottom of their columns.

Hints

  1. Do not modify the grid while you are still detecting runs. First mark every cell that should be removed.
  2. After marking, rebuild each column from bottom to top by copying only the cells that survive.

Loading coding console...