Design Tic-Tac-Toe
Detect a winner in O(1) per move by tracking row/column/diagonal sums.
4 min read
design simulation
Problem#
Design TicTacToe(n) and move(row, col, player) -> winner. Two players (1 and 2) alternate marking cells. move returns the player number if the move wins the game, else 0.
Examples#
n = 3, moves(0,0,1) (0,2,2) (2,2,1) (1,1,2) (2,0,1) (1,0,2) (2,1,1)→ returns0, 0, 0, 0, 0, 0, 1.
Constraints#
1 <= n <= 100. Up toO(n^2)moves.
Hints#
Hint
Track signed sums per row, column, and both diagonals. Player 1 adds +1, player 2 adds -1.
Approach#
Maintain rows[n], cols[n], diag, anti. On move(r, c, p): add +1 for player 1 or -1 for player 2 to rows[r], cols[c], and the diagonals when applicable. If any tracker reaches +n (player 1 wins) or -n (player 2 wins), return the player.
Solution#
class TicTacToe { vector<int> rows, cols; int diag = 0, anti = 0, n;public: TicTacToe(int n_) : rows(n_, 0), cols(n_, 0), n(n_) {}
int move(int row, int col, int player) { int v = player == 1 ? 1 : -1; rows[row] += v; cols[col] += v; if (row == col) diag += v; if (row + col == n - 1) anti += v; int target = player == 1 ? n : -n; if (rows[row] == target || cols[col] == target || diag == target || anti == target) return player; return 0; }};type TicTacToe struct { rows, cols []int diag, anti int n int}
func Constructor(n int) TicTacToe { return TicTacToe{rows: make([]int, n), cols: make([]int, n), n: n}}
func (t *TicTacToe) Move(row, col, player int) int { v := 1 if player == 2 { v = -1 } t.rows[row] += v t.cols[col] += v if row == col { t.diag += v } if row+col == t.n-1 { t.anti += v } target := t.n if player == 2 { target = -t.n } if t.rows[row] == target || t.cols[col] == target || t.diag == target || t.anti == target { return player } return 0}class TicTacToe: def __init__(self, n: int): self.n = n self.rows = [0] * n self.cols = [0] * n self.diag = 0 self.anti = 0
def move(self, row: int, col: int, player: int) -> int: v = 1 if player == 1 else -1 self.rows[row] += v self.cols[col] += v if row == col: self.diag += v if row + col == self.n - 1: self.anti += v target = self.n if player == 1 else -self.n if (self.rows[row] == target or self.cols[col] == target or self.diag == target or self.anti == target): return player return 0var TicTacToe = function(n) { this.n = n; this.rows = new Array(n).fill(0); this.cols = new Array(n).fill(0); this.diag = 0; this.anti = 0;};
TicTacToe.prototype.move = function(row, col, player) { const v = player === 1 ? 1 : -1; this.rows[row] += v; this.cols[col] += v; if (row === col) this.diag += v; if (row + col === this.n - 1) this.anti += v; const target = player === 1 ? this.n : -this.n; if (this.rows[row] === target || this.cols[col] === target || this.diag === target || this.anti === target) { return player; } return 0;};class TicTacToe { private int[] rows; private int[] cols; private int diag = 0, anti = 0, n;
public TicTacToe(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
public int move(int row, int col, int player) { int v = player == 1 ? 1 : -1; rows[row] += v; cols[col] += v; if (row == col) diag += v; if (row + col == n - 1) anti += v; int target = player == 1 ? n : -n; if (rows[row] == target || cols[col] == target || diag == target || anti == target) { return player; } return 0; }}class TicTacToe { private n: number; private rows: number[]; private cols: number[]; private diag = 0; private anti = 0;
constructor(n: number) { this.n = n; this.rows = new Array(n).fill(0); this.cols = new Array(n).fill(0); }
move(row: number, col: number, player: number): number { const v = player === 1 ? 1 : -1; this.rows[row] += v; this.cols[col] += v; if (row === col) this.diag += v; if (row + col === this.n - 1) this.anti += v; const target = player === 1 ? this.n : -this.n; if (this.rows[row] === target || this.cols[col] === target || this.diag === target || this.anti === target) { return player; } return 0; }}Editorial#
The signed-sum trick collapses both players’ moves into one structure. A winning row/column/diagonal forces all n cells to the same player, producing +n or -n. Only the four touched trackers need updating per move — the rest are unaffected — giving O(1) per move.
Complexity#
- Time: O(1) per move.
- Space: O(n).
Concept revision#
Related#