Quick 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.

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

  1. Only lines that pass through (row, col) can matter; a line of four anywhere else on the board is ignored.
  2. There are just four line directions through a cell, and a run along one of them may continue on both sides of (row, col).
  3. 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.

Four in a Row Through the Last Move

mediumSnowflakeSoftware Engineer

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

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

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++.

Examples

Example 1
Input
([[1]], 0, 0)
Output
False
Notes
Minimum 1 x 1 board: the placed piece alone is a run of length 1 in every direction.
Example 2
Input
([[2, 2, 2], [2, 2, 2], [2, 2, 2]], 1, 1)
Output
False
Notes
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.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def is_winning_move(board: list[list[int]], row: int, col: int) -> bool:
Sample call
is_winning_move([[1]], 0, 0)
Language
Case 1
Input
([[1]], 0, 0)
Expected
False
Case 2
Input
([[2, 2, 2], [2, 2, 2], [2, 2, 2]], 1, 1)
Expected
False

Browse More Questions

Show the approach

Approach

Let p = board[row][col]. Check the four direction vectors (0, 1) horizontal, (1, 0) vertical, (1, 1) top-left to bottom-right and (1, -1) top-right to bottom-left. For each one, start a count at 1 for the placed piece, walk forward from (row, col) while the next cell is on the board and equals p, then walk backward the same way, adding one per matching cell. Invariant: every counted cell equals p and is contiguous with (row, col) along that line, and each walk stops at the first cell that is off the board, empty or the opponent's, so the final count is exactly the length of the maximal run of p containing (row, col) in that direction. Return True as soon as any direction reaches at least 4; if none does, return False. Cells off these four lines are never inspected, so lines of four elsewhere on the board are ignored as the rules require, and the opponent's pieces only ever end a run. Edge cases: a board narrower than 4 in some direction can never reach 4 there (a 1 x 1 board returns False); moves on edges and corners rely on the explicit bounds check, which matters in Python because a negative index would silently wrap to the opposite side of the board; runs longer than 4 still return True. Each walk visits at most max(m, n) cells, so the work is linear in the board dimensions and needs constant extra memory.

Time complexity:
O(m + n)
Space complexity:
O(1)