Design Tic-Tac-Toe
Implement a function run_ops(n, moves) that simulates a Tic-Tac-Toe game on an $n \times n$ board with two players.
n: the board size.moves: a list of moves, where each move is[row, col, player], applied in order.playeris1or2.
For each move, place the player's mark at (row, col) and record a result:
- The player number (1 or 2) if that move wins the game by completing an entire row, column, or diagonal with their marks.
0otherwise.
Return the list of results, one per move, in order.
Constraints:
- $2 \leq n \leq 100$
playeris either1or2- $0 \leq \text{row}, \text{col} < n$
- Each move is on an empty square
- At most $n^2$ moves
Design your solution so that processing each move runs in $O(1)$ time.
Example
``` run_ops(3, [[0,0,1],[0,2,2],[2,2,1],[1,1,2],[2,0,1],[1,0,2],[2,1,1]]) -> [0, 0, 0, 0, 0, 0, 1] ```
Player 1's seventh move at (2,1) completes the bottom row (cells (2,0), (2,1), (2,2) are all Player 1), so that move returns 1; all earlier moves return 0.
Hints
- You do not need to store the full board. Think about what information is sufficient to detect a win -- what makes a row, column, or diagonal complete?
- If you keep a running count of marks per row, column, and diagonal, you can check for a win in constant time. Consider using $+1$ for one player and $-1$ for the other.
- Maintain arrays
rows[n]andcols[n]plus two diagonal counters. After each move, update the relevant counters and check if any has absolute value equal to $n$.
Worked Solution
How to Think About It: The brute-force approach checks the entire board after every move -- scan the row, column, and both diagonals to see if any are completely filled by one player. That is $O(n)$ per move. Can we do better? The key observation is that we do not need to know the full board state. We only need to know, for each row, column, and diagonal, how many marks each player has placed. If we track running sums, we can check for a win in $O(1)$ after each move.
The trick is to use a single counter per line: player 1 adds $+1$, player 2 adds $-1$. A row/column/diagonal is complete when its sum reaches $+n$ (player 1 wins) or $-n$ (player 2 wins). This avoids maintaining separate counters per player.
Algorithm:
1. Maintain arrays rows[n] and cols[n], and two scalars diag and anti, all initialized to 0. 2. For each move [row, col, player] in order: - Compute val = +1 if player 1, -1 if player 2. - Add val to rows[row] and cols[col]. - If row == col, add val to diag. - If row + col == n - 1, add val to anti. - If any of these four counters has absolute value $n$, append player to the results; otherwise append 0. 3. Return the list of results.
Contract note: The judge calls run_ops(n, moves) and compares the returned list of per-move results (one integer per move) to the expected list. Return the list -- do not print.
Code:
```python def run_ops(n, moves): # n: board size. moves: list of [row, col, player] applied in order to an n x n # Tic-Tac-Toe board. For each move return the winner (1 or 2) if that move # completes a full row, column, or diagonal, else 0. Return the list of results, # one per move, in order. rows = [0] * n cols = [0] * n diag = 0 anti = 0 results = [] for row, col, player in moves: val = 1 if player == 1 else -1 rows[row] += val cols[col] += val if row == col: diag += val if row + col == n - 1: anti += val if (abs(rows[row]) == n or abs(cols[col]) == n or abs(diag) == n or abs(anti) == n): results.append(player) else: results.append(0) return results ```
Complexity:
- Time: $O(1)$ per move (a constant number of additions and comparisons), $O(m)$ over all $m$ moves.
- Space: $O(n)$ for the
rowsandcolsarrays; the diagonal counters are $O(1)$.
Answer: Use $+1/-1$ tallies for each row, column, and diagonal. A win occurs when any tally reaches $\pm n$. Collect one result per move (the winning player or 0) and return the list.
Intuition
The core idea is a classic space-time tradeoff: instead of scanning $O(n)$ cells after every move, we maintain just enough bookkeeping to answer the win query instantly. The $+1/-1$ encoding is elegant because it collapses two players into a single counter per line. A sum of $+n$ means player 1 filled the line; $-n$ means player 2 did; anything in between means neither has. This is the same "aggregate counter" pattern that shows up everywhere in systems design -- instead of recalculating from scratch, maintain a running summary and update it incrementally.
In interview settings, this problem tests whether you can identify that a win only depends on a one-dimensional summary (row/column/diagonal counts) rather than the full two-dimensional board state. The follow-up question is usually about generalizing to $k$-in-a-row on an $n \times n$ board, which is genuinely harder because the number of "lines" to track is no longer $O(n)$. For the standard $n$-in-a-row version, the $+1/-1$ counter approach is the cleanest solution.