Connect Four Game

Problem Description

Note: The following is a reconstructed version of an Airbnb coding interview question about implementing a Connect Four game, based on multiple candidate reports and interview-prep summaries. Exact wording and API details may differ from any proprietary internal statement.

Connect Four is a two-player connection board game played on a vertical grid with 6 rows and 7 columns. Two players take turns dropping their discs into one of the 7 columns. A disc always falls straight down to occupy the lowest available (empty) cell in that column. The first player to align four of their own discs consecutively in a straight line horizontally, vertically, or diagonally wins the game.[1][2][3]

Design and implement the core game logic for Connect Four:

• Maintain the game board state.
• Handle player moves given a column index.
• After each move, determine whether that move causes the current player to win.
• If needed, detect when the board is full and the game ends in a draw.

Focus on correctness, clean code structure, and efficient winner detection rather than UI. You may assume there are exactly two players, labeled as player 1 and player 2.[2][3]

Input/Output Format

Design a class ConnectFour to encapsulate the game.

You may assume a standard board of 6 rows and 7 columns.

Class and Constructor

text class ConnectFour

• Constructor

  text ConnectFour()

  • Initializes an empty 6 × 7 board.
  • All cells start empty.

Board Representation

Use a 2D matrix of integers with dimensions rows = 6, cols = 7:

• board[r][c] = 0 means the cell is empty.
• board[r][c] = 1 means the cell is occupied by player 1.
• board[r][c] = 2 means the cell is occupied by player 2.

Row indices can be defined such that:

• r = 0 is the top row.
• r = 5 is the bottom row.

A move in a given column always occupies the highest row index r in that column for which board[r][c] == 0.

Move API

Implement the following method:

text int move(int col, int player)

• Arguments

  • col (int):
    • Zero-based column index where the current player wants to drop a disc.
    • Valid range: 0 <= col < 7.
  • player (int):
    • Player identifier: 1 or 2.

• Behavior

  • Validate the column:
    • If col is outside [0, 6], you may assume it will not be passed in production, or you may treat it as an invalid move (implementation detail).
  • Find the lowest empty row r in that column:
    • The largest index r such that board[r][col] == 0.
  • Place the current player’s disc:
    • Set board[r][col] = player.
  • Check for a winner after this move:
    • If the current player now has four consecutive discs in a row (horizontally, vertically, or diagonally), this move wins the game.

• Return value

  • 0 if there is no winner yet after this move.
  • player (i.e., 1 or 2) if this move causes that player to win.
  • Optionally, you may also return:
    • -1 to indicate an invalid move (e.g., dropping into a full column) if you choose to handle invalid input explicitly.

You do not need to provide methods for resetting the game or printing the board unless asked as a follow-up.

Examples

Example 1 — Horizontal Win

Consider the following sequence of operations:

`text Input: ["ConnectFour", "move", "move", "move", "move", "move", "move", "move"] [[], [0, 1], [0, 2], [1, 1], [1, 2], [2, 1], [2, 2], [3, 1]]

Output: [null, 0, 0, 0, 0, 0, 0, 1] `

Explanation

• Start with an empty 6 × 7 board.

• move(0, 1):

  • Player 1 drops a disc into column 0.
  • It falls to the bottom row (row 5, column 0).
  • No four-in-a-row yet ⇒ return 0.

• move(0, 2):

  • Player 2 drops a disc into column 0.
  • It falls to row 4, column 0.
  • No four-in-a-row ⇒ return 0.

• move(1, 1):

  • Player 1 drops a disc into column 1.
  • It falls to row 5, column 1.
  • Still no four-in-a-row ⇒ return 0.

• move(1, 2):

  • Player 2 drops a disc into column 1.
  • It falls to row 4, column 1.
  • No winner ⇒ return 0.

• move(2, 1):

  • Player 1 drops a disc into column 2.
  • It falls to row 5, column 2.
  • No winner yet ⇒ return 0.

• move(2, 2):

  • Player 2 drops a disc into column 2.
  • It falls to row 4, column 2.
  • Still no four-in-a-row ⇒ return 0.

• move(3, 1):

  • Player 1 drops a disc into column 3.

  • It falls to row 5, column 3.

  • Now the bottom row has:

    • (5,0) = 1, (5,1) = 1, (5,2) = 1, (5,3) = 1

  • That is four consecutive discs from player 1 horizontally.

  • Player 1 wins ⇒ return 1.

Example 2 — Vertical Win

`text Input: ["ConnectFour", "move", "move", "move", "move", "move", "move", "move"] [[], [3, 1], [2, 2], [3, 1], [2, 2], [3, 1], [2, 2], [3, 1]]

Output: [null, 0, 0, 0, 0, 0, 0, 1] `

Explanation

• move(3, 1):
  • Player 1 places at (5,3). No winner ⇒ 0.
• move(2, 2):
  • Player 2 places at (5,2). No winner ⇒ 0.
• move(3, 1):
  • Player 1 places at (4,3). No winner ⇒ 0.
• move(2, 2):
  • Player 2 places at (4,2). No winner ⇒ 0.
• move(3, 1):
  • Player 1 places at (3,3). No winner ⇒ 0.
• move(2, 2):
  • Player 2 places at (3,2). No winner ⇒ 0.
• move(3, 1):
  • Player 1 places at (2,3).

Now in column 3, from bottom to top:

• (5,3) = 1, (4,3) = 1, (3,3) = 1, (2,3) = 1

That is four consecutive discs for player 1 vertically. Player 1 wins ⇒ return 1.

Constraints

You may assume:

• Board dimensions are fixed:
  • rows = 6
  • cols = 7.[2]
• Number of players: exactly 2 (player ∈ {1, 2}).
• Moves:
  • 0 <= col < 7
  • There will be at most 6 * 7 = 42 valid moves in a single game (board fills up).
  • You may assume the interviewer either:
    • Guarantees that moves are always applied to non-full columns, or
    • Expects you to handle a “column full” condition (e.g., by returning -1 or throwing an exception).
• Time and space:
  • Space complexity:
    • $$ O(R \times C) $$ to store the board (here, $$ R = 6, C = 7 $$).
  • Time per move:
    • Placing a disc is $$ O(R) $$ in the simplest implementation (scan from bottom upward to find the first empty cell in the column).
    • Winner detection can be done in $$ O(1) $$ per move in practice, because each check only looks at up to a constant number of cells in four directions around the last move (bounded by board size).
  • With the small fixed board (6 × 7), even re-scanning the entire board after each move is effectively constant time, but you should still discuss the general big-O complexity.[4][5]

You should be prepared to discuss how the approach scales if the board size were parameterized (e.g., m × n grid and arbitrary “connect k” value).

Solution Hint

Maintain a 2D integer matrix to represent the board; for each move(col, player), drop the disc to the lowest empty row in that column, then from the placed cell scan in four directions (horizontal, vertical, two diagonals) counting consecutive discs for that player to see if any line reaches length 4.