Detect Four in a Row Through the Last Move on an m x n Board
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Two players take turns placing pieces on an m x n board. Each cell holds 0 (empty), 1 (a piece of Player 1) or 2 (a piece of Player 2). A player wins when at least four of their pieces lie consecutively in a horizontal, vertical or diagonal line. Given the board right after a player has placed a piece at `(row, col)`, determine whether that move formed such a line.
The report does not say whether pieces drop to the lowest empty cell of a column; that does not matter here, because the function receives the board after the move. The exact rule is fixed in Rules below.
### Function Signature
```python
def is_winning_move(board: list[list[int]], row: int, col: int) -> bool:
```
### Rules
- `board[row][col]` is the piece just placed, 1 or 2; call its value `p`.
- Consider the four line directions through `(row, col)`: horizontal, vertical, the diagonal running from top-left to bottom-right, and the diagonal running from top-right to bottom-left.
- Return `True` if, in at least one of these directions, the maximal run of consecutive cells equal to `p` that contains `(row, col)` has length at least 4; otherwise return `False`.
- Lines of four that do not pass through `(row, col)` are ignored. The board does not have to be reachable by legal play.
### Constraints
- `1 <= m, n <= 1000`, where `m = len(board)` and every row has length `n`
- Every cell is 0, 1 or 2.
- `0 <= row < m`, `0 <= col < n`, and `board[row][col]` is 1 or 2.
### Examples
**Example 1**
```text
Input: board = [[0, 0, 0, 0, 0],
[2, 2, 0, 2, 0],
[1, 1, 1, 1, 1]]
row = 2, col = 2
Output: True
```
Row 2 holds five consecutive 1s through `(2, 2)`; a run longer than four also wins.
**Example 2**
```text
Input: board = [[2, 0, 0, 0],
[1, 2, 0, 0],
[1, 1, 2, 0],
[1, 1, 1, 2]]
row = 1, col = 1
Output: True
```
The diagonal from `(0, 0)` to `(3, 3)` holds four 2s, and the run extends on both sides of `(1, 1)`.
**Example 3**
```text
Input: board = [[0, 0, 0, 1],
[0, 0, 1, 0],
[0, 2, 0, 0],
[1, 0, 0, 0]]
row = 0, col = 3
Output: False
```
The diagonal from `(0, 3)` to `(3, 0)` holds 1, 1, 2, 1, so the run through `(0, 3)` has length 2. The row, the column and the other diagonal through `(0, 3)` each give a run of length 1.
Overview: Given an m x n board holding empty cells and two players' pieces, decide whether the piece just placed at a given row and column completes four or more in a row horizontally, vertically or along either diagonal. It tests grid traversal, bounds checks and counting a run on both sides of a cell.
Two players take turns placing pieces on an `m x n` board. Each cell holds `0` (empty), `1` (a piece of Player 1) or `2` (a piece of Player 2). A player wins when at least four of their pieces lie consecutively in a horizontal, vertical or diagonal line.
You are given `board` right after a player has placed a piece at `(row, col)`. Determine whether that move formed such a line. Whether pieces drop to the lowest empty cell of a column does not matter: you receive the board after the move, and the board does not have to be reachable by legal play.
**Rules**
- `board[row][col]` is the piece just placed, `1` or `2`; call its value `p`.
- Consider the four line directions through `(row, col)`: horizontal, vertical, the diagonal running from top-left to bottom-right, and the diagonal running from top-right to bottom-left.
- Return `True` if, in at least one of these directions, the maximal run of consecutive cells equal to `p` that contains `(row, col)` has length at least 4; otherwise return `False`.
- Lines of four that do not pass through `(row, col)` are ignored.
Return a boolean (`True`/`False` in Python, `true`/`false` in JavaScript, Java and C++).
**Example 1**
```text
Input: board = [[2, 0, 0, 0],
[1, 2, 0, 0],
[1, 1, 2, 0],
[1, 1, 1, 2]]
row = 1, col = 1
Output: True
```
The diagonal from `(0, 0)` to `(3, 3)` holds four 2s, and the run extends on both sides of `(1, 1)`.
**Example 2**
```text
Input: board = [[0, 0, 0, 1],
[0, 0, 1, 0],
[0, 2, 0, 0],
[1, 0, 0, 0]]
row = 0, col = 3
Output: False
```
The diagonal from `(0, 3)` to `(3, 0)` holds 1, 1, 2, 1, so the run through `(0, 3)` has length 2. The row, the column and the other diagonal through `(0, 3)` each give a run of length 1.
**Constraints**
- `1 <= m, n <= 1000`, where `m = len(board)` and every row has length `n`
- Every cell is 0, 1 or 2.
- `0 <= row < m`, `0 <= col < n`, and `board[row][col]` is 1 or 2.
No value can exceed 2^31 - 1, so a 32-bit `int` is sufficient in Java and C++.
Constraints
- 1 <= m, n <= 1000, where m = len(board) and every row has length n
- Every cell is 0, 1 or 2.
- 0 <= row < m, 0 <= col < n, and board[row][col] is 1 or 2.
Examples
Input: ([[1]], 0, 0)
Expected Output: False
Explanation: Minimum 1 x 1 board: the placed piece alone is a run of length 1 in every direction.
Input: ([[2, 2, 2], [2, 2, 2], [2, 2, 2]], 1, 1)
Expected Output: False
Explanation: 3 x 3 board full of Player 2: every direction through the center is a run of exactly 3; a board smaller than 4 in both dimensions can never win.
Hints
- Only lines that pass through (row, col) can matter; a line of four anywhere else on the board is ignored.
- There are just four line directions through a cell, and a run along one of them may continue on both sides of (row, col).
- A run ends at the board edge or at the first cell that is not p, whether that cell is empty or holds the opponent's piece.