Design Tic-Tac-Toe

Table of Contents +

Design Tic-Tac-Toe looks like a kids game, but the interviewer is testing something deeper. They want to see if you can avoid re-checking the whole board after every single move. The slow way works fine. The fast way is what gets you the offer.

🎯 The Problem

You build a game on an n by n board and answer one question after each move.

The setup:

  • The board is n by n.
  • Two players take turns placing a mark.
  • After each move you must answer fast whether that move won the game.

How a player wins:

  • Fill a whole row with their own mark.
  • Or fill a whole column.
  • Or fill one of the two diagonals.
  • The main diagonal runs top-left to bottom-right. The anti-diagonal runs top-right to bottom-left.
Input:  n = 3, moves = [(0,0,1), (0,1,2), (1,1,1), (0,2,2), (2,2,1)]
Output: 0, 0, 0, 0, 1


Explanation: each move is (row, col, player). The function returns the
winning player after a move, or 0 if no win yet. Player 1 takes (0,0),
then (1,1), then (2,2). Those three cells are the main diagonal. So the
last move fills the whole main diagonal for player 1, and we return 1.

Here is the board after the moves. Each cell shows the player who took it. This first diagram shows the game state we are reasoning about.

3x3 board after all moves

(0,0) P1

(0,1) P2

(0,2) P2

(1,0) empty

(1,1) P1

(1,2) empty

(2,0) empty

(2,1) empty

(2,2) P1

Player 1 took (0,0), then (1,1), then (2,2). Those three cells form the main diagonal, the line from the top-left corner to the bottom-right corner. So on that last move player 1 completes the whole diagonal and wins. Every move before it returns 0, because no line was full yet.

🐢 Approach 1: Full Board Scan (Brute Force)

The idea in one line: keep the whole board, and after each move scan that move’s lines to check for a win.

The idea:

  • Store the full board in a 2D grid.
  • Put the player’s mark in the cell they chose.
  • Scan that move’s whole row, whole column, and both diagonals.

How it works:

  • A row check looks at n cells. A column check looks at another n.
  • The diagonals add more cells.
  • If a line is all the same player, that player wins.

Why it is weak:

  • Each move costs about O(n) work for the scan.
  • On a huge board with many moves, that scan adds up.
  • We want each move to cost the same tiny amount no matter the board size.

Here is the full-board-scan code:

tic_tac_toe_board_scan.py
class TicTacToe:
    def __init__(self, n):
        self.board = [[0] * n for _ in range(n)]
        self.n = n


    def move(self, row, col, player):
        self.board[row][col] = player
        lines = []
        lines.extend(self.board)
        lines.extend([[self.board[r][c] for r in range(self.n)] for c in range(self.n)])
        lines.append([self.board[i][i] for i in range(self.n)])
        lines.append([self.board[i][self.n - 1 - i] for i in range(self.n)])
        return player if any(all(cell == player for cell in line) for line in lines) else 0

⚡ Approach 2: Row, Column and Diagonal Counters (Best)

The idea in one line: drop the board, keep one running total per line, and a full line lands on exactly +n or -n.

The idea:

  • You never need the full board. You only need to know when a line is full.
  • Keep one counter per row, one per column, one for the main diagonal, one for the anti-diagonal.
  • A counter is a running total that goes up or down.

How the scoring works:

  • Player 1 adds +1 to the counters their move touches.
  • Player 2 adds -1 to the same counters.
  • A full line of player 1 reaches +n. A full line of player 2 reaches -n.
  • Opposite signs mean a mixed line can never hit either value.

How a move checks for a win:

  • Update the row counter and the column counter for the move.
  • A cell is on the main diagonal when its row equals its column.
  • A cell is on the anti-diagonal when its row plus its column equals n - 1.
  • Check if any touched counter equals +n or -n.

Why it is fast:

  • Each move touches at most four counters and checks four values.
  • No scanning at all, so each move is O(1).
  • Constant time no matter how big the board is.

This second diagram shows what one move does. It updates a handful of counters, then checks them.

yes

no

Player makes a move at row r, col c

add +1 for P1 or -1 for P2

update rows[r]

update cols[c]

if r == c update diag

if r + c == n-1 update antiDiag

any counter == n or == -n ?

that player wins

game continues, return 0

Steps to Solve

  1. Create arrays rows and cols, each of size n, filled with zeros. Create two single counters diag and antiDiag, both zero.
  2. When a move comes in, decide the score. Use +1 for player 1 and -1 for player 2.
  3. Add that score to rows[r] and to cols[c].
  4. If r equals c, add the score to diag.
  5. If r + c equals n - 1, add the score to antiDiag.
  6. Check if any of those four counters now equals n (player 1 wins) or -n (player 2 wins). If so, return that player.
  7. Otherwise return 0, meaning no winner yet.

This Python version uses a class with simple lists for the counters.

tic_tac_toe.py
class TicTacToe:
    def __init__(self, n):
        self.n = n
        self.rows = [0] * n        # one counter per row
        self.cols = [0] * n        # one counter per column
        self.diag = 0              # main diagonal counter
        self.anti_diag = 0         # anti-diagonal counter


    def move(self, r, c, player):
        score = 1 if player == 1 else -1   # P1 adds, P2 subtracts
        self.rows[r] += score
        self.cols[c] += score
        if r == c:                         # on the main diagonal
            self.diag += score
        if r + c == self.n - 1:            # on the anti-diagonal
            self.anti_diag += score
        n = self.n
        if n in (self.rows[r], self.cols[c], self.diag, self.anti_diag):
            return 1                       # player 1 filled a line
        if -n in (self.rows[r], self.cols[c], self.diag, self.anti_diag):
            return 2                       # player 2 filled a line
        return 0                           # no winner yet




game = TicTacToe(3)
print(game.move(0, 0, 1))  # P1
print(game.move(0, 1, 2))  # P2
print(game.move(1, 1, 1))  # P1
print(game.move(0, 2, 2))  # P2
print(game.move(2, 2, 1))  # P1 completes main diagonal

The output of the above code will be:

0
0
0
0
1

Let us walk through the Python move method line by line, because the counter trick is the whole interview.

score = 1 if player == 1 else -1

This sets the direction. Player 1 pushes counters up. Player 2 pushes them down. So the two players move every line in opposite directions and can never both fill the same line.

self.rows[r] += score
self.cols[c] += score

The move sits in exactly one row and one column. So we update just those two counters. We never touch the other rows or columns. That is why the work stays tiny.

if r == c:
    self.diag += score
if r + c == self.n - 1:
    self.anti_diag += score

A cell is on the main diagonal only when its row equals its column. A cell is on the anti-diagonal only when row plus column equals n - 1. These two checks decide whether the diagonals are even affected by this move.

if n in (self.rows[r], self.cols[c], self.diag, self.anti_diag):
    return 1
if -n in (self.rows[r], self.cols[c], self.diag, self.anti_diag):
    return 2
return 0

A counter reaches n only when player 1 owns the whole line. It reaches -n only when player 2 owns the whole line. We check just the four counters this move could have changed. Nothing else can have flipped, so checking the rest is wasted work. That is how the win check stays O(1).

⏱️ Time and Space Complexity

The brute force keeps the full grid and scans a line on every move, so each move costs O(n) time and the board costs O(n²) space. The counter version touches a fixed handful of values per move, so each move is O(1) time. It only stores one number per row and per column, so it uses O(n) space. So you trade the big grid for a few small counters and you make every move instant.

Approach Time per Move Space Complexity
Full board scan O(n) O(n²)
Row / col / diagonal counters O(1) O(n)

Tip

The opposite-sign idea is the part to say out loud. Tell the interviewer you give player 1 a +1 and player 2 a -1 so a full line lands on exactly +n or -n. That single sentence shows you understand why no scan is needed.

🧩 Key Takeaways

  • ✅ You never need the full board. Running counters for each line are enough to detect a win.
  • ✅ Give player 1 a +1 and player 2 a -1, so a full line hits +n or -n and the two players can never mix.
  • ✅ A move only affects its own row, its own column, and at most the two diagonals.
  • ✅ The diagonal checks are r == c for the main diagonal and r + c == n - 1 for the anti-diagonal.
  • ✅ This turns each move from O(n) scanning into O(1) counter updates.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why give player 1 a +1 and player 2 a -1 on each counter?

    Why: Opposite signs mean a line owned fully by player 1 sums to +n, and by player 2 to -n. A mixed line can never reach either value.

  2. 2

    How do you know a cell is on the anti-diagonal?

    Why: The anti-diagonal runs top-right to bottom-left, where row + col always equals n - 1. The main diagonal is where row == col.

  3. 3

    What is the time cost of a single move with the counter approach?

    Why: A move updates at most four counters and checks four values, all constant work, so it is O(1).

  4. 4

    What space does the counter solution use for an n by n board?

    Why: We store n row counters and n column counters plus two diagonal counters, which is O(n) total.

Score: 0 / 4

🚀 What’s Next?

Previous All O'one Data Structure Next Nested List Weight Sum