Design Tic-Tac-Toe

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Design Tic-Tac-Toe is a medium design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (signed line counters), runs in O(1) per move time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (store the board, check the lines through the move) up.

Problem

Design a TicTacToe class for an n x n board shared by two players, numbered 1 and 2. The first player to fill an entire row, an entire column, or one of the two main diagonals with their own marks wins.

  • TicTacToe(int n) creates an empty board of size n.
  • int move(int row, int col, int player) places player’s mark on the empty cell (row, col) and returns player if this move wins the game, or 0 if nobody has won yet.

Moves are always legal: the cell is empty and the game has not been won yet. Can you make every move faster than O(n²)?

Examples

Example 1

Input
TicTacToe(3), move(1, 1, 1), move(0, 2, 2), move(0, 0, 1), move(2, 0, 2), move(2, 2, 1)
Output
0, 0, 0, 0, 1
Why
Player 1 holds (0,0), (1,1) and (2,2), the full main diagonal, on the fifth move.

Example 2

Input
TicTacToe(2), move(0, 1, 2), move(1, 1, 1), move(0, 0, 2)
Output
0, 0, 2
Why
On a 2 x 2 board, player 2 fills the whole top row with two marks.

Constraints

  • 2 <= n <= 100
  • player is 1 or 2.
  • 0 <= row, col < n, and every move goes to an empty cell.
  • No move is made after a player has won.
  • At most n^2 calls to move.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (store the board, check the lines through the move)O(n) per moveO(n²)
Optimal (signed line counters)O(1) per moveO(n)

1Brute force (store the board, check the lines through the move)

TimeO(n) per moveAt most four lines of length n are scanned after each move.
SpaceO(n²)The whole board is stored.

Keep the full n x n grid. After placing a mark, walk the row, the column and, if the cell is on one, each diagonal, and see whether all n cells belong to the current player.

  1. board[row][col] = player.
  2. Check every cell of the row, then of the column.
  3. If row == col, check the main diagonal; if row + col == n - 1, check the anti-diagonal.
  4. Return player if any checked line is full of their marks, else 0.
class TicTacToe {
    private final int n;
    private final int[][] board;

    public TicTacToe(int n) {
        this.n = n;
        this.board = new int[n][n];
    }

    public int move(int row, int col, int player) {
        board[row][col] = player;
        boolean rowWin = true, colWin = true, diagWin = row == col, antiWin = row + col == n - 1;
        for (int i = 0; i < n; i++) {
            if (board[row][i] != player) rowWin = false;
            if (board[i][col] != player) colWin = false;
            if (board[i][i] != player) diagWin = false;
            if (board[i][n - 1 - i] != player) antiWin = false;
        }
        return (rowWin || colWin || diagWin || antiWin) ? player : 0;
    }
}

2Optimal (signed line counters)

TimeO(1) per moveEach move updates and checks at most four counters.
SpaceO(n)Two arrays of n counters plus two diagonal counters.

Drop the board. Keep one counter per row, one per column and one for each diagonal. Player 1 adds +1 and player 2 adds -1 to every line the move touches. Since cells are never reused, a line whose counter reaches n in absolute value is filled entirely by one player.

  1. rows[n], cols[n], diag, anti all start at 0.
  2. d = player == 1 ? 1 : -1.
  3. rows[row] += d; cols[col] += d; if row == col, diag += d; if row + col == n - 1, anti += d.
  4. If any of those four values has absolute value n, return player; else return 0.
class TicTacToe {
    private final int n;
    private final int[] rows, cols;
    private int diag, anti;

    public TicTacToe(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
    }

    public int move(int row, int col, int player) {
        int d = player == 1 ? 1 : -1;
        rows[row] += d;
        cols[col] += d;
        if (row == col) diag += d;
        if (row + col == n - 1) anti += d;
        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
                || Math.abs(diag) == n || Math.abs(anti) == n) {
            return player;
        }
        return 0;
    }
}

Edge cases to test

  • A win on the anti-diagonal (row + col == n - 1)
  • The center cell of an odd board lies on both diagonals
  • n = 2, where two marks already complete a line
  • A full board with no winner, so every move returns 0

Hints

Hint 1

After a move, only the row, the column and (maybe) the two diagonals through that cell can have become complete.

Hint 2

You never need the board itself: count how many marks each player has in every row, column and diagonal.

Hint 3

Use +1 for player 1 and -1 for player 2 in a single counter per line; a line is won when its counter reaches +n or -n.

FAQ

What is the best time complexity for Design Tic-Tac-Toe?

Optimal (signed line counters) runs in O(1) per move time and O(n) extra space. Each move updates and checks at most four counters.

Which pattern does Design Tic-Tac-Toe use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Design Tic-Tac-Toe?

Yes. Brute force (store the board, check the lines through the move) takes O(n) per move time and O(n²) space. Keep the full n x n grid.

Which edge cases should I test for Design Tic-Tac-Toe?

A win on the anti-diagonal (row + col == n - 1); The center cell of an odd board lies on both diagonals; n = 2, where two marks already complete a line; A full board with no winner, so every move returns 0.