Design Tic-Tac-Toe

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    Design a tic-tac-toe game for two players on an n × n board. move(row, col, player) places the player's mark and returns the winner after that move: 1 or 2, or 0 if nobody has won yet. A player wins by filling a whole row, a whole column, or either diagonal. Moves are always valid (the cell is empty and the game isn't over). Follow-up: the board is R × C and a player wins with k marks in a row in any direction.

    A small design question that rewards thinking about what to store. The obvious answer rescans the board; the good answer keeps a handful of counters so each move is O(1). Original problem: LeetCode 348 (subscription). The R × C, k-in-a-row version is the same idea as Connect Four.

    Example

    Seven moves on a 3 × 3 board. Player 1's seventh move completes the bottom row, so that call returns 1.
    Seven moves on a 3 × 3 board. Player 1's seventh move completes the bottom row, so that call returns 1.
    TicTacToe(3)
    move(0, 0, 1) -> 0
    move(0, 2, 2) -> 0
    move(2, 2, 1) -> 0
    move(1, 1, 2) -> 0
    move(2, 0, 1) -> 0
    move(1, 0, 2) -> 0
    move(2, 1, 1) -> 1      # bottom row is all player 1
    KInARow(rows=4, cols=5, k=4)
    moves by player 1: (3,0), (2,1), (1,2), (0,3)   (player 2 plays elsewhere in between)
    the fourth of them returns 1                     # a rising diagonal of 4

    Constraints (assumed)

    • 2 ≤ n ≤ 100; at most n² calls to move.
    • Follow-up: 1 ≤ R, C ≤ 1,000 and 1 ≤ k ≤ max(R, C).

    What this question tests

    • Asking what the next query needs and storing exactly that, instead of the whole board.
    • Small but exact index rules: which cells lie on the main diagonal (r == c) and the anti-diagonal (r + c == n − 1).
    • Choosing a different approach when the rules change (k in a row on a rectangle), and saying why counters no longer fit.

    Questions to ask first

    1. Are moves always valid? (Here: yes. Otherwise check the cell is empty and the game isn't already won.)
    2. Do both diagonals count? (Here: yes.)
    3. Is the board square, and is the win the full length? That decides counters vs a local scan.
    4. Should move also report a draw? (Here: no; you could add a move counter.)