Design Tic-Tac-Toe

Detect a winner in O(1) per move by tracking row/column/diagonal sums.

Medium
Time O(1) per move Space O(n)
LeetCode
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) → returns 0, 0, 0, 0, 0, 0, 1.

Constraints#

  • 1 <= n <= 100. Up to O(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#

Design Tic-Tac-Toe
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.