Match-3 Grid: Find Horizontal and Vertical Runs, Then Clear and Drop Cells
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `m × n` grid of positive integers representing a Match-3 game board. A **match** is a run of 3 or more equal values side by side in one row (a horizontal match) or in one column (a vertical match).
Do two things:
1. **Find the matches.** Report every match as its value and its length.
2. **Clear and drop.** Set every cell that belongs to any match to `0`. Then, in each column, let the non-zero values fall to the bottom, keeping their original top-to-bottom order, so that all the zeros end up at the top of the column.
Return the list of matches and the resulting grid.
### Function Signature
```python
def match_three(grid: list[list[int]]) -> tuple[list[list[int]], list[list[int]]]:
```
Return a pair `(matches, result)`. Each element of `matches` is a two-element list `[value, length]`. `result` is the grid after clearing and dropping, as a list of `m` rows of `n` integers, top row first.
### Rules
- A run is a maximal sequence of equal values in consecutive cells of one row or one column. A run is a match when its length is at least 3, and it counts once at its full length: four 7s side by side are the single match `[7, 4]`, not two matches of length 3.
- Two runs of the same value that are separated by a different value are separate matches.
- Order of `matches`: first all horizontal matches, scanning rows top to bottom and each row left to right; then all vertical matches, scanning columns left to right and each column top to bottom. Each match takes its place from the first cell of its run in this scan.
- A cell can belong to both a horizontal and a vertical match. Report both matches; the cell is cleared like any other matched cell.
- Matches are found once, in the input grid. Clear and drop exactly once, and do not look for new matches in the dropped grid.
- If there are no matches, `matches` is empty and `result` equals the input grid.
### Constraints
- `1 <= m, n <= 100`, and every row has exactly `n` values
- `1 <= grid[i][j] <= 10^9`
### Examples
**Example 1**
```text
Input: grid = [[1, 2, 3, 4], [7, 7, 7, 7], [5, 2, 7, 1], [6, 2, 7, 3]]
Output: ([[7, 4], [7, 3]], [[0, 0, 0, 0], [1, 2, 0, 4], [5, 2, 0, 1], [6, 2, 3, 3]])
```
Rows and columns are numbered from 0. Row 1 is four 7s, a horizontal match of length 4. Column 2 holds 7, 7, 7 in rows 1 to 3, a vertical match of length 3. Column 1 is 2, 7, 2, 2: the 2s are not three in a row, so it has no match. Clearing gives `[[1, 2, 3, 4], [0, 0, 0, 0], [5, 2, 0, 1], [6, 2, 0, 3]]`, and dropping moves each column's non-zero values to the bottom: for example, column 0 becomes 0, 1, 5, 6 and column 2 becomes 0, 0, 0, 3.
**Example 2**
```text
Input: grid = [[2, 3, 4], [1, 1, 1], [5, 1, 6], [7, 1, 8]]
Output: ([[1, 3], [1, 3]], [[0, 0, 0], [2, 0, 4], [5, 0, 6], [7, 3, 8]])
```
Row 1 is a horizontal match of three 1s, and column 1 has a vertical match of three 1s in rows 1 to 3. Cell `(1, 1)` belongs to both, so both matches are reported. After clearing, the 3 at the top of column 1 falls to the bottom row.
**Example 3**
```text
Input: grid = [[3, 3, 3, 4, 3, 3, 3]]
Output: ([[3, 3], [3, 3]], [[0, 0, 0, 4, 0, 0, 0]])
```
The 4 separates two runs of three 3s, so they are two matches, listed left to right. Every column has a single cell, so nothing falls.
Overview: A two-part grid problem modeled on a Match-3 game: report every horizontal and vertical run of three or more equal values in a fixed scan order, then clear the matched cells and let the remaining values in each column fall to the bottom. It tests precise run detection, ordering rules and grid simulation.
Read the full Roblox Software Engineer interview experience this question came from
You are given an `m x n` grid of positive integers that represents a Match-3 game board. A **match** is a run of 3 or more equal values side by side in one row (a horizontal match) or in one column (a vertical match).
Do two things:
1. **Find the matches.** Report every match as its value and its length.
2. **Clear and drop.** Set every cell that belongs to any match to `0`. Then, in each column, let the non-zero values fall to the bottom, keeping their original top-to-bottom order, so that all the zeros end up at the top of the column.
Return the list of matches and the resulting grid as the pair `(matches, result)`. Each element of `matches` is a two-element list `[value, length]`. `result` is the grid after clearing and dropping, as a list of `m` rows of `n` integers, top row first. Python returns the tuple `(matches, result)`; JavaScript returns the two-element array `[matches, result]`; Java returns a `java.util.Map.Entry` whose key is `matches` and whose value is `result`; C++ returns a `std::pair` whose `first` is `matches` and whose `second` is `result`.
### Rules
- A run is a maximal sequence of equal values in consecutive cells of one row or one column. A run is a match when its length is at least 3, and it counts once at its full length: four 7s side by side are the single match `[7, 4]`, not two matches of length 3.
- Two runs of the same value that are separated by a different value are separate matches.
- Order of `matches`: first all horizontal matches, scanning rows top to bottom and each row left to right; then all vertical matches, scanning columns left to right and each column top to bottom. Each match takes its place from the first cell of its run in this scan.
- A cell can belong to both a horizontal and a vertical match. Report both matches; the cell is cleared like any other matched cell.
- Matches are found once, in the input grid. Clear and drop exactly once, and do not look for new matches in the dropped grid.
- If there are no matches, `matches` is empty and `result` equals the input grid.
### Example 1
```text
Input: grid = [[1, 2, 3, 4], [7, 7, 7, 7], [5, 2, 7, 1], [6, 2, 7, 3]]
Output: ([[7, 4], [7, 3]], [[0, 0, 0, 0], [1, 2, 0, 4], [5, 2, 0, 1], [6, 2, 3, 3]])
```
Rows and columns are numbered from 0. Row 1 is four 7s, a horizontal match of length 4. Column 2 holds 7, 7, 7 in rows 1 to 3, a vertical match of length 3. Column 1 is 2, 7, 2, 2: the 2s are not three in a row, so it has no match. Clearing gives `[[1, 2, 3, 4], [0, 0, 0, 0], [5, 2, 0, 1], [6, 2, 0, 3]]`, and dropping moves each column's non-zero values to the bottom: column 0 becomes 0, 1, 5, 6 and column 2 becomes 0, 0, 0, 3.
### Example 2
```text
Input: grid = [[2, 3, 4], [1, 1, 1], [5, 1, 6], [7, 1, 8]]
Output: ([[1, 3], [1, 3]], [[0, 0, 0], [2, 0, 4], [5, 0, 6], [7, 3, 8]])
```
Row 1 is a horizontal match of three 1s, and column 1 has a vertical match of three 1s in rows 1 to 3. Cell `(1, 1)` belongs to both, so both matches are reported. After clearing, the 3 at the top of column 1 falls to the bottom row.
### Constraints
- `1 <= m, n <= 100`, and every row has exactly `n` values
- `1 <= grid[i][j] <= 10^9`
No value or match length can exceed 2^31 - 1 (values are at most 10^9 and lengths at most 100), so a 32-bit `int` is sufficient in Java and C++.
Constraints
- 1 <= m, n <= 100, and every row has exactly n values
- 1 <= grid[i][j] <= 10^9
Examples
Input: ([[5]],)
Expected Output: ([], [[5]])
Explanation: Minimum 1x1 grid: no run can reach length 3, so matches is empty and the grid is returned unchanged.
Input: ([[4, 4]],)
Expected Output: ([], [[4, 4]])
Explanation: 1x2 grid: a horizontal run of exactly 2 is not a match.
Hints
- A match is a maximal run, so a run of four or more equal values is one match at its full length. Find where each run of equal values starts and ends before you check its length.
- Matches are found only in the original grid, and one cell can belong to both a horizontal and a vertical match. Make sure clearing one match cannot stop you from finding another.
- Each column drops on its own: its surviving values keep their top-to-bottom order and end up at the bottom, with zeros above them.