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 Onsite rounds at Roblox.

What role is this question designed for?

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

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.

Input: ([],)

Expected Output: []

Explanation: An empty grid has no runs.

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

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

Explanation: There is a horizontal run of four 2s in the first row, a vertical run of four 2s in the first column, and a horizontal run of three 3s in the second row.

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

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

Explanation: The first four cells in the only column form one maximal vertical run.

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

Expected Output: []

Explanation: No row or column contains three or more equal contiguous digits.

Solution

def solution(grid):
    if not grid or not grid[0]:
        return []

    rows = len(grid)
    cols = len(grid[0])
    runs = []

    for r in range(rows):
        for c in range(cols):
            # Check whether this cell is the start of a horizontal run.
            if c == 0 or grid[r][c] != grid[r][c - 1]:
                end = c
                while end < cols and grid[r][end] == grid[r][c]:
                    end += 1
                length = end - c
                if length >= 3:
                    runs.append([r, c, length, 0])

            # Check whether this cell is the start of a vertical run.
            if r == 0 or grid[r][c] != grid[r - 1][c]:
                end = r
                while end < rows and grid[end][c] == grid[r][c]:
                    end += 1
                length = end - r
                if length >= 3:
                    runs.append([r, c, length, 1])

    return runs

Time complexity: O(rows * cols). Space complexity: O(1) extra space, excluding the output list.

Hints

Scan each row once and each column once, counting the length of the current streak of equal values.
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.

Input: ([[4],[0],[5],[5],[5]],)

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

Explanation: The three 5s form a vertical run and are removed. The surviving 4 and 0 then fall to the bottom while keeping order, so 4 stays above 0.

Input: ([[7]],)

Expected Output: [[7]]

Explanation: A single cell cannot form a run of length at least 3, so nothing is removed.

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

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

Explanation: Every row and every column is a run of the same digit with length 3, so all cells are removed.

Solution

def solution(grid):
    if not grid or not grid[0]:
        return []

    m, n = len(grid), len(grid[0])
    marked = [[False] * n for _ in range(m)]

    # Mark horizontal runs
    for r in range(m):
        c = 0
        while c < n:
            k = c + 1
            while k < n and grid[r][k] == grid[r][c]:
                k += 1
            if k - c >= 3:
                for j in range(c, k):
                    marked[r][j] = True
            c = k

    # Mark vertical runs
    for c in range(n):
        r = 0
        while r < m:
            k = r + 1
            while k < m and grid[k][c] == grid[r][c]:
                k += 1
            if k - r >= 3:
                for i in range(r, k):
                    marked[i][c] = True
            r = k

    # Build result after gravity
    result = [[0] * n for _ in range(m)]
    for c in range(n):
        kept = []
        for r in range(m):
            if not marked[r][c]:
                kept.append(grid[r][c])

        start = m - len(kept)
        for i, value in enumerate(kept):
            result[start + i][c] = value

    return result

Time complexity: O(m * n). Space complexity: O(m * n).

Hints

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

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.