Design Tic-Tac-Toe - Practice Coding Problems

Design Tic-Tac-Toe - Problem

Design a Tic-Tac-Toe game that is played between two players on an n × n board. You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves are allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

TicTacToe(int n) Initializes the object with the size of the board n.
int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return 0 if there is no winner after the move, 1 if player 1 is the winner after the move, or 2 if player 2 is the winner after the move.

Input & Output

Example 1 — Player 1 Wins on 3x3 Board

$ Input: n = 3, moves: [[0,0,1], [0,2,2], [2,2,1], [1,1,2], [2,0,1], [1,0,2], [1,2,1]]

› Output: [null,0,0,0,0,0,0,1]

💡 Note: Player 1 places marks at (0,0), (2,2), (2,0), (1,2). The last move (1,2) completes the anti-diagonal [0,0]→[1,1]→[2,2], so Player 1 wins.

Example 2 — Row Win on 2x2 Board

$ Input: n = 2, moves: [[0,0,1], [1,1,2], [0,1,1]]

› Output: [null,0,0,1]

💡 Note: Player 1 fills the entire top row: (0,0) and (0,1). Two marks in a row on a 2x2 board means Player 1 wins.

Example 3 — Column Win

$ Input: n = 3, moves: [[0,0,1], [1,1,2], [1,0,1], [2,2,2], [2,0,1]]

› Output: [null,0,0,0,0,1]

💡 Note: Player 1 places marks at (0,0), (1,0), (2,0) - filling the entire first column and winning.

Constraints

2 ≤ n ≤ 100
player is 1 or 2
0 ≤ row, col < n
(row, col) are unique for each different call to move
At most n² calls will be made to move

Visualization

Tap to expand

Understanding the Visualization

Input

Board size n and sequence of player moves (row, col, player)

Process

Track sums for each row, column, and diagonal using counters

Output

Return winner (1 or 2) or 0 if game continues

Key Takeaway

🎯 Key Insight: Use mathematical sums instead of board scanning for instant winner detection

Asked in

M Microsoft 45 a Amazon 38 G Google 32 Apple 28

The optimal approach uses counter arrays to track row, column, and diagonal sums in O(1) time per move. Player 1 adds +1, Player 2 adds -1. When any counter reaches ±n, that player wins. Time: O(1), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Track Row/Column Sums	O(1)	O(n)	Use counters to track sum of each row, column, and diagonal instead of storing the board
Brute Force - Check Entire Board	O(n)	O(n²)	Store the entire board and check all rows, columns, and diagonals after each move

Optimized - Track Row/Column Sums — Algorithm Steps

Step 1: Create arrays to track sums for rows, columns, and diagonals
Step 2: For each move, update the corresponding counters (+1 for player 1, -1 for player 2)
Step 3: Check if any counter equals ±n to determine winner

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Counters

Add +1 or -1 to row/column/diagonal sums

Check Target

See if any counter equals ±n

Instant Result

Winner found in O(1) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int n;
    int* rows;
    int* cols;
    int diag;
    int antiDiag;
} TicTacToe;

TicTacToe* ticTacToeCreate(int n) {
    TicTacToe* obj = (TicTacToe*)malloc(sizeof(TicTacToe));
    obj->n = n;
    obj->rows = (int*)calloc(n, sizeof(int));
    obj->cols = (int*)calloc(n, sizeof(int));
    obj->diag = 0;
    obj->antiDiag = 0;
    return obj;
}

int ticTacToeMove(TicTacToe* obj, int row, int col, int player) {
    int add = player == 1 ? 1 : -1;
    int target = player == 1 ? obj->n : -obj->n;
    
    obj->rows[row] += add;
    obj->cols[col] += add;
    if (row == col) {
        obj->diag += add;
    }
    if (row + col == obj->n - 1) {
        obj->antiDiag += add;
    }
    
    if (obj->rows[row] == target ||
        obj->cols[col] == target ||
        obj->diag == target ||
        obj->antiDiag == target) {
        return player;
    }
    
    return 0;
}

int main() {
    printf("[null,0,0,0,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each move only updates 2-4 counters and checks their values

✓ Linear Growth

Space Complexity

O(n)

Only need arrays for row sums, column sums, and 2 diagonal sums

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Track Row/Column Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler