Quick Overview

Given a Connect Four board and the cell where a player just dropped a piece, decide whether that move completes four or more of the player's pieces in a row horizontally, vertically or diagonally. It tests grid traversal in fixed directions, bounds checking, and counting runs that pass through a single cell.

Check Whether the Last Move Wins a Game of Connect Four

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Connect Four is played on a vertical grid. Two players take turns dropping pieces into it, and a player wins by lining up four of their own pieces in a row: horizontally, vertically or diagonally. Given the board right after a player has placed a piece at `(row, col)`, decide whether that piece gives the player four in a row. ### Function Signature ```python def did_player_connect_four(board: list[list[int]], row: int, col: int, player: int) -> bool: ``` ### Rules - `board[r][c]` is `0` for an empty cell, or `1` or `2` for a piece of that player. Row `0` is the top row and column `0` is the leftmost column. - `board[row][col] == player`: it is the piece that was just placed. - Consider the four lines 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, on at least one of them, `(row, col)` is part of a run of at least 4 consecutive cells that all equal `player`. Runs longer than 4 also count. - Runs that do not include `(row, col)` are ignored, even if they contain four or more of the player's pieces. - The board does not have to come from a legal game: pieces need not rest on other pieces, and the two players' piece counts need not match. ### Constraints - `1 <= len(board) <= 100` and `1 <= len(board[r]) <= 100`; all rows have the same length. - Every cell is `0`, `1` or `2`. - `0 <= row < len(board)` and `0 <= col < len(board[0])`. - `player` is `1` or `2`, and `board[row][col] == player`. ### Examples **Example 1** ```text Input: board = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 2, 2, 2, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0]] row = 5, col = 4, player = 1 Output: True ``` Row 5 holds player 1's pieces in columns 1 through 4, a horizontal run of four that includes `(5, 4)`. **Example 2** ```text Input: board = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0, 0], [0, 0, 2, 1, 0, 0, 0], [0, 2, 1, 1, 0, 0, 0], [2, 1, 1, 1, 2, 2, 0]] row = 2, col = 3, player = 2 Output: True ``` The cells `(2, 3)`, `(3, 2)`, `(4, 1)` and `(5, 0)` all hold player 2's pieces, a diagonal run of four running from top-right to bottom-left. **Example 3** ```text Input: board = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [2, 2, 2, 0, 0, 0, 2], [1, 1, 1, 1, 0, 0, 2]] row = 3, col = 6, player = 1 Output: False ``` Player 1 has four in a row along the bottom row, but that run does not pass through `(3, 6)`. Every line through `(3, 6)` contains only that one piece of player 1.

Overview: Given a Connect Four board and the cell where a player just dropped a piece, decide whether that move completes four or more of the player's pieces in a row horizontally, vertically or diagonally. It tests grid traversal in fixed directions, bounds checking, and counting runs that pass through a single cell.

Read the full Snowflake Software Engineer interview experience this question came from

Connect Four is played on a vertical grid. Two players take turns dropping pieces into it, and a player wins by lining up four of their own pieces in a row: horizontally, vertically or diagonally. You are given the board right after a player has placed a piece at `(row, col)`. Decide whether that piece gives the player four in a row, and return `True` or `False`. ### Rules - `board[r][c]` is `0` for an empty cell, or `1` or `2` for a piece of that player. Row `0` is the top row and column `0` is the leftmost column. - `board[row][col] == player`: it is the piece that was just placed. - Consider the four lines 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, on at least one of them, `(row, col)` is part of a run of at least 4 consecutive cells that all equal `player`; otherwise return `False`. Runs longer than 4 also count. - Runs that do not include `(row, col)` are ignored, even if they contain four or more of the player's pieces. - The board does not have to come from a legal game: pieces need not rest on other pieces, and the two players' piece counts need not match. ### Constraints - `1 <= len(board) <= 100` and `1 <= len(board[r]) <= 100`; all rows have the same length. - Every cell is `0`, `1` or `2`. - `0 <= row < len(board)` and `0 <= col < len(board[0])`. - `player` is `1` or `2`, and `board[row][col] == player`. - No value can exceed 2^31 - 1, so 32-bit integers suffice in every language. ### Example 1 ```text Input: board = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 2, 2, 2, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0]] row = 5, col = 4, player = 1 Output: True ``` Row 5 holds player 1's pieces in columns 1 through 4, a horizontal run of four that includes `(5, 4)`. ### Example 2 ```text Input: board = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [2, 2, 2, 0, 0, 0, 2], [1, 1, 1, 1, 0, 0, 2]] row = 3, col = 6, player = 1 Output: False ``` Player 1 has four in a row along the bottom row, but that run does not pass through `(3, 6)`. Every line through `(3, 6)` contains only that one piece of player 1.

Constraints

  • 1 <= len(board) <= 100 and 1 <= len(board[r]) <= 100; all rows have the same length
  • Every cell is 0, 1 or 2
  • 0 <= row < len(board) and 0 <= col < len(board[0])
  • player is 1 or 2, and board[row][col] == player
  • No value can exceed 2^31 - 1

Examples

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

Expected Output: False

Explanation: Minimum 1x1 board: the only piece forms a run of 1 on every line, so False.

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

Expected Output: False

Explanation: 3x3 board full of player 2: every line through the centre has only 3 cells, so no run reaches 4; adding lines together would wrongly give True.

Hints

  1. Only the four lines that pass through (row, col) matter; a four in a row anywhere else on the board does not change the answer.
  2. The placed piece can sit anywhere inside a run, not only at one end of it.
  3. Pieces on two different lines never combine: one single line needs an unbroken run of at least four of the player's pieces.

Loading coding console...

Show the approach

Approach

Only the four lines through (row, col) can matter. For each direction vector (0, 1), (1, 0), (1, 1) and (1, -1), start a count at 1 for the placed piece, then walk forward from (row, col) while the next cell is on the board and equals player, and walk backward along the opposite vector the same way. Invariant: after both walks, count equals the length of the maximal run of player's cells on that line that contains (row, col), because each walk stops at the first cell that is off the board, empty, or the opponent's. Correctness: (row, col) is part of a run of at least 4 consecutive player cells on a line exactly when that maximal run has length at least 4, so returning True as soon as any line's count reaches 4 (longer runs also qualify), and False after all four lines, matches the rules. Counts from different lines are never added, cells beyond a gap or an opponent piece are never counted, and runs elsewhere on the board are never examined, which is exactly the rule that only runs through (row, col) count. Edge cases: boards with fewer than 4 rows or columns just give short walks (a 1x1 board returns False); explicit bounds checks stop each walk at the board edge, including diagonals clipped near corners, so no scan wraps around to another row or column.

Time complexity:
O(R + C)
Space complexity:
O(1)