# LeetCode 348: Design Tic-Tac-Toe

## Problem Restatement

We need to design a Tic-Tac-Toe game played by two players on an `n x n` board.

The class supports two operations:

| Method | Meaning |
|---|---|
| `TicTacToe(n)` | Initializes an `n x n` board |
| `move(row, col, player)` | Places `player` at position `(row, col)` and returns the winner |

The rules are:

| Rule | Meaning |
|---|---|
| Valid move | Every move is guaranteed to be placed on an empty cell |
| Game state | No moves are made after a winner exists |
| Winner | A player wins by filling one row, column, main diagonal, or anti-diagonal |
| Return value | `0` for no winner, `1` if player 1 wins, `2` if player 2 wins |

The problem asks us to avoid scanning the whole board after each move. A counter-based design gives `O(1)` time per move.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Board size `n`, then moves `(row, col, player)` |
| Output | Winner after each move |
| Player IDs | `1` and `2` |
| Winning line | Any full row, full column, main diagonal, or anti-diagonal |

Class shape:

```python
class TicTacToe:

    def __init__(self, n: int):
        ...

    def move(self, row: int, col: int, player: int) -> int:
        ...
```

## Examples

Example:

```text
Input:
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0,0,1], [0,2,2], [2,2,1], [1,1,2], [2,0,1], [1,0,2], [2,1,1]]

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

Board size is `3`.

Moves:

| Move | Player | Result |
|---|---:|---:|
| `(0, 0)` | `1` | `0` |
| `(0, 2)` | `2` | `0` |
| `(2, 2)` | `1` | `0` |
| `(1, 1)` | `2` | `0` |
| `(2, 0)` | `1` | `0` |
| `(1, 0)` | `2` | `0` |
| `(2, 1)` | `1` | `1` |

At the last move, player `1` fills row `2`:

```text
X X X
```

So `move(2, 1, 1)` returns `1`.

## First Thought: Store the Board and Scan

A direct method is to store the full board.

After every move:

1. Check the whole row.
2. Check the whole column.
3. Check the main diagonal if needed.
4. Check the anti-diagonal if needed.

This works, but each move can cost:

```text
O(n)
```

The board itself also costs:

```text
O(n^2)
```

We can do better because we only need to know whether a line has been completed.

## Key Insight

A player wins when one of their counters reaches `n`.

We can store:

| Counter | Meaning |
|---|---|
| `rows[i]` | Net marks in row `i` |
| `cols[j]` | Net marks in column `j` |
| `diagonal` | Net marks on main diagonal |
| `anti_diagonal` | Net marks on anti-diagonal |

Use `+1` for player `1`.

Use `-1` for player `2`.

Then:

| Counter value | Meaning |
|---:|---|
| `n` | Player 1 filled that line |
| `-n` | Player 2 filled that line |

This avoids storing the whole board.

Because moves are guaranteed valid, we do not need to check whether a cell is already occupied.

## Algorithm

Initialize:

```python
rows = [0] * n
cols = [0] * n
diagonal = 0
anti_diagonal = 0
```

For each move:

1. Convert player to score:
   1. `+1` for player `1`
   2. `-1` for player `2`
2. Add score to `rows[row]`.
3. Add score to `cols[col]`.
4. If `row == col`, add score to `diagonal`.
5. If `row + col == n - 1`, add score to `anti_diagonal`.
6. If any affected counter has absolute value `n`, return `player`.
7. Otherwise return `0`.

## Walkthrough

Use `n = 3`.

Initial state:

```text
rows = [0, 0, 0]
cols = [0, 0, 0]
diagonal = 0
anti_diagonal = 0
```

Move:

```text
move(0, 0, 1)
```

Player `1` has score `+1`.

Update:

```text
rows[0] = 1
cols[0] = 1
diagonal = 1
```

No counter reaches `3`, so return `0`.

Move:

```text
move(2, 2, 1)
```

Update:

```text
rows[2] = 1
cols[2] = 1
diagonal = 2
```

Still no winner.

Move:

```text
move(2, 0, 1)
```

Update:

```text
rows[2] = 2
cols[0] = 2
anti_diagonal = 1
```

Move:

```text
move(2, 1, 1)
```

Update:

```text
rows[2] = 3
cols[1] = 1
```

Now:

```text
abs(rows[2]) == 3
```

So player `1` wins.

Return `1`.

## Correctness

A player wins exactly when they have placed marks in all `n` cells of one row, one column, or one diagonal.

The algorithm updates exactly the counters affected by the current move:

| Move position | Updated counters |
|---|---|
| Any cell `(row, col)` | `rows[row]`, `cols[col]` |
| `row == col` | `diagonal` |
| `row + col == n - 1` | `anti_diagonal` |

For player `1`, every mark contributes `+1`.

So a line filled entirely by player `1` has counter value `n`.

For player `2`, every mark contributes `-1`.

So a line filled entirely by player `2` has counter value `-n`.

A mixed line cannot have absolute value `n`, because marks from the two players cancel each other.

After each move, only the row, column, and possible diagonals containing that move can become newly winning lines. Checking those counters is therefore sufficient.

Thus, the algorithm returns the correct winner after every move.

## Complexity

| Operation | Time | Why |
|---|---:|---|
| Constructor | `O(n)` | Creates row and column counter arrays |
| `move()` | `O(1)` | Updates and checks a constant number of counters |

| Space | Value | Why |
|---|---:|---|
| Extra space | `O(n)` | Stores `n` row counters and `n` column counters |

## Implementation

```python
class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row: int, col: int, player: int) -> int:
        score = 1 if player == 1 else -1

        self.rows[row] += score
        self.cols[col] += score

        if row == col:
            self.diagonal += score

        if row + col == self.n - 1:
            self.anti_diagonal += score

        if (
            abs(self.rows[row]) == self.n
            or abs(self.cols[col]) == self.n
            or abs(self.diagonal) == self.n
            or abs(self.anti_diagonal) == self.n
        ):
            return player

        return 0
```

## Code Explanation

Store the board size:

```python
self.n = n
```

Create counters for rows and columns:

```python
self.rows = [0] * n
self.cols = [0] * n
```

Create counters for the two diagonals:

```python
self.diagonal = 0
self.anti_diagonal = 0
```

Convert the player into a signed score:

```python
score = 1 if player == 1 else -1
```

Update the affected row and column:

```python
self.rows[row] += score
self.cols[col] += score
```

If the move is on the main diagonal:

```python
if row == col:
    self.diagonal += score
```

If the move is on the anti-diagonal:

```python
if row + col == self.n - 1:
    self.anti_diagonal += score
```

Check whether any affected counter reaches `n` in absolute value:

```python
if abs(self.rows[row]) == self.n:
    return player
```

The implementation combines all four checks into one condition.

## Testing

```python
def run_tests():
    game = TicTacToe(3)

    assert game.move(0, 0, 1) == 0
    assert game.move(0, 2, 2) == 0
    assert game.move(2, 2, 1) == 0
    assert game.move(1, 1, 2) == 0
    assert game.move(2, 0, 1) == 0
    assert game.move(1, 0, 2) == 0
    assert game.move(2, 1, 1) == 1

    game = TicTacToe(3)

    assert game.move(0, 0, 1) == 0
    assert game.move(1, 0, 1) == 0
    assert game.move(2, 0, 1) == 1

    game = TicTacToe(3)

    assert game.move(0, 2, 2) == 0
    assert game.move(1, 1, 2) == 0
    assert game.move(2, 0, 2) == 2

    game = TicTacToe(1)

    assert game.move(0, 0, 1) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style sequence | Checks row win after several moves |
| Column win | Checks vertical counter |
| Anti-diagonal win | Checks `row + col == n - 1` |
| `n = 1` | First move immediately wins |