Hack University
295/670

295. Design Tic-Tac-Toe

Medium

Build the referee for a game of tic-tac-toe on an n × n board, played by two players who place marks one at a time.

Implement a TicTacToe class: the constructor receives n, and move(row, col, player) records that player (either 1 or 2) marked the cell at (row, col). The call returns player if that very placement completes a full row, a full column, or one of the two main diagonals with that player's marks — and 0 otherwise.

Every move is legal (the cell is empty), and no further moves arrive after someone has won. Your class is driven by a scripted sequence of moves read from input; the return value of each call is printed on its own line.

Follow-up: can you decide each move in better than O(n) — without ever rescanning the board?

Example 1 — player 1 completes the bottom rowThe seven scripted moves of example 1. The first six complete no line, so each returns 0. The seventh, move(2, 1, 1), gives player 1 all of row 2 and returns 1.
TicTacToe(3) — after move(2, 1, 1)col 0col 1col 2row 0row 1row 2XOOOXXXX = player 1, O = player 2Moves 1–6 return 0:no line is complete yet.move(2, 1, 1) fills row 2→ returns 1

Example 1:

Input: TicTacToe(3); move(0,0,1), move(0,2,2), move(2,2,1), move(1,1,2), move(2,0,1), move(1,0,2), move(2,1,1)

Output: [0, 0, 0, 0, 0, 0, 1]

Explanation: Players alternate without completing a line for six moves. move(2, 1, 1) is player 1's third mark in row 2 — the row is full, so the call returns 1.

Example 2:

Input: TicTacToe(2); move(0,0,1), move(1,1,2), move(0,1,1)

Output: [0, 0, 1]

Explanation: On a 2 × 2 board a line needs only two marks: move(0, 1, 1) completes row 0 for player 1.

Constraints:

  • 1 ≤ n ≤ 100
  • player is 1 or 2
  • 0 ≤ row, col < n
  • Every move targets an empty cell, and at most n² moves are made
  • No moves are issued after a player has won

Hints:

When a mark lands, only the lines through that cell can newly become complete: its row, its column, and (sometimes) the two diagonals. Nothing else on the board changed.

You don't even need the board. Keep one counter per row, per column, and per diagonal; add +1 for player 1 and -1 for player 2. A line belongs entirely to one player exactly when its counter hits +n or -n — an O(1) check per move.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: TicTacToe(3); move(0,0,1), move(0,2,2), move(2,2,1), move(1,1,2), move(2,0,1), move(1,0,2), move(2,1,1)

Expected output: [0, 0, 0, 0, 0, 0, 1]