Katkat
Back

Detect a Winner on a 3x3 Tic-Tac-Toe Board

HebbiaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently represent board states and implement win-condition logic for a grid-based game.

Tic-Tac-Toe Win Validator

Given a 3x3 Tic-Tac-Toe board represented as a list of 9 integers, write a function to determine the winner. The board is represented as a flat array where index i corresponds to row i // 3 and column i % 3. Use the following mapping:

  • 0: Empty cell
  • 1: Player X
  • 2: Player O

Your function should return:

  • 1 if Player X has won.
  • 2 if Player O has won.
  • 0 if the game is a draw or currently incomplete.

Function Signature

def get_winner(board: List[int]) -> int:

Constraints

  • board will always have exactly 9 elements.
  • Values will only be 0, 1, or 2.

Examples

Example 1: Input: [1, 1, 1, 0, 2, 0, 2, 0, 0] Output: 1 Explanation: Player X (1) has completed the first row.

Example 2: Input: [1, 2, 0, 1, 2, 0, 0, 0, 0] Output: 0 Explanation: No player has three in a row.

Edge Cases

  • Consider scenarios where multiple lines might technically be "won" (e.g., crossing lines), or where the board is full with no winner.

Hints

Hint 1

Represent the winning combinations as a list of index triplets, such as [[0, 1, 2], [3, 4, 5], ...].

Hint 2

Iterate through the winning triplets and check if the values at those indices are identical and non-zero.

Hint 3

Ensure your logic handles boards where no winner exists by returning 0 only after checking all winning conditions.

Follow-up questions

  • How would you modify your solution to work on an N x N board?
  • If this board state was updated frequently in a real-time system, how could you optimize the winner check to be O(1) instead of checking all rows and columns every time?
  • How would you detect if a game has reached a stalemate (draw) where no more moves are possible?