Design Tic-Tac-Toe

medium design matrix

Problem

Design an n×n tic-tac-toe board where each move(row, col, player) returns whether that player just won (or 0 for no winner).

Inputmoves = [(0,0,1),(0,2,2),(2,2,1),(1,1,2),(2,0,1),(1,0,2),(2,1,1)]

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

Player 1 completes the bottom row on move 7.

moves (r,c,p ;)

class TicTacToe:
    def __init__(self, n):
        self.n = n
        self.rows = [[0, 0] for _ in range(n)]
        self.cols = [[0, 0] for _ in range(n)]
        self.diag = [0, 0]
        self.anti = [0, 0]
    def move(self, r, c, p):
        i = p - 1
        self.rows[r][i] += 1
        self.cols[c][i] += 1
        if r == c: self.diag[i] += 1
        if r + c == self.n - 1: self.anti[i] += 1
        if self.n in (self.rows[r][i], self.cols[c][i], self.diag[i], self.anti[i]):
            return p
        return 0

class TicTacToe {
  constructor(n) {
    this.n = n;
    this.rows = Array.from({length: n}, () => [0, 0]);
    this.cols = Array.from({length: n}, () => [0, 0]);
    this.diag = [0, 0]; this.anti = [0, 0];
  }
  move(r, c, p) {
    const i = p - 1;
    this.rows[r][i]++; this.cols[c][i]++;
    if (r === c) this.diag[i]++;
    if (r + c === this.n - 1) this.anti[i]++;
    if ([this.rows[r][i], this.cols[c][i], this.diag[i], this.anti[i]].includes(this.n)) return p;
    return 0;
  }
}

class TicTacToe {
    int n; int[][] rows, cols; int[] diag = new int[2], anti = new int[2];
    public TicTacToe(int n) { this.n = n; rows = new int[n][2]; cols = new int[n][2]; }
    public int move(int r, int c, int p) {
        int i = p - 1;
        rows[r][i]++; cols[c][i]++;
        if (r == c) diag[i]++;
        if (r + c == n - 1) anti[i]++;
        if (rows[r][i] == n || cols[c][i] == n || diag[i] == n || anti[i] == n) return p;
        return 0;
    }
}

class TicTacToe {
    int n; vector> rows, cols; int diag[2] = {0,0}, anti[2] = {0,0};
public:
    TicTacToe(int n) : n(n), rows(n, {0,0}), cols(n, {0,0}) {}
    int move(int r, int c, int p) {
        int i = p - 1;
        rows[r][i]++; cols[c][i]++;
        if (r == c) diag[i]++;
        if (r + c == n - 1) anti[i]++;
        if (rows[r][i] == n || cols[c][i] == n || diag[i] == n || anti[i] == n) return p;
        return 0;
    }
};

Explanation

The naive way to check for a win is to scan the whole board after every move. That is wasteful. The trick here is to keep running counters so each move is checked in O(1) — we never look at the full grid.

For each player we track how many marks they have in every row, every column, the main diagonal, and the anti-diagonal. The arrays rows[r], cols[c], diag, and anti each hold two slots, one per player (i = p - 1 picks the slot).

On move(r, c, p) we bump that player's count for row r and column c. If the cell is on the main diagonal (r == c) we bump diag; if it is on the anti-diagonal (r + c == n - 1) we bump anti.

If any of those four counters reaches n, that player just completed a full line and wins, so we return p; otherwise we return 0.

Example on a 3×3 board: player 1's marks at (0,0), (2,0)... wait — when player 1 plays (2,0), then (2,2), then (2,1), the counter rows[2] for player 1 reaches 3 = n, completing the bottom row, so that move returns 1 while all earlier moves returned 0.

Time: O(1) per move Space: O(n)