Incremental n x n Tic-Tac-Toe Game-Over Check in O(n), Then O(1) per Move

An `n x n` tic-tac-toe game is played by players `1` and `2`. A player wins by occupying all `n` cells of a row, a column, the main diagonal (cells `(i, i)`) or the anti-diagonal (cells `(i, n - 1 - i)`). If every cell is occupied and nobody has won, the game is a draw. A first solution decides whether the game is over by scanning every row, every column and both diagonals for a winner and then scanning the board for an empty cell, which takes O(n²) time. The interviewer then asked you to optimize the time complexity of this check. An O(n) answer was judged still too slow, and the final target was O(1). Those bounds require the check to stop re-reading the whole board, so assume the incremental setting of this follow-up: the game starts from an empty board, your code is called after every move with the move just played, and it may keep its own state between calls. ```python class GameOverChecker: def __init__(self, n: int) -> None: ... def move(self, row: int, col: int, player: int) -> bool: ... ``` `move` returns `True` if, after this move, one player occupies an entire row, column or diagonal, or no empty cell is left, and `False` otherwise. ### Constraints and Clarifications - `n >= 1`; rows and columns are 0-indexed, and `player` is `1` or `2`. - `move` reports only whether the game is over, not who won. - Draw detection is still required; a check that only finds wins is incomplete. - As in the interview, write your own test cases before running the code, one for each possible outcome. ### Clarifying Questions - Can a call target an occupied or out-of-range cell, or arrive after the game is already over? If so, should `move` reject it, and may that validation cost extra memory? - Do the players strictly alternate, or must the check work for any order of moves? - For the O(1)-time version, is O(n) extra memory acceptable, and does the checker need to keep the board itself? ### Part 1 — Check in O(n) per move Implement `move` so that each call runs in O(n) time. Explain why your check cannot miss a win that the full O(n²) scan would find, and how you detect a draw without scanning for an empty cell. ```hint Which lines can change Compare the board just before and just after the call: exactly one cell changed. Which lines contain that cell, and could any other line have become a winning line? ``` #### What This Part Should Cover - Which lines a single move can turn into a winning line, and why checking only those is complete - How the cell just played is matched to each diagonal, including a cell that lies on both - Draw detection within the O(n) bound - The state kept between calls and the per-move time ### Part 2 — Check in O(1) per move The interviewer considered O(n) per move too slow. Change the state you keep so that each `move` call does a constant amount of work and still detects both wins and draws. Implement it and state its time and memory cost. ```hint Summarize each line Instead of re-reading the `n` cells of an affected line, keep a small number per line that one move can update in constant time, and choose it so that a line owned entirely by one player shows up as a value that no other state of that line can produce. ``` #### What This Part Should Cover - The per-line state and how one move updates it in constant time - How a completed line is recognized for either player, and why a line holding both players' marks can never look complete - Draw detection and the `n = 1` board - Time per move, total time over a full game, and extra memory compared with Part 1 ### What a Strong Answer Covers - A correctness argument for both versions that covers rows, columns, both diagonals and draws - Complexity stated precisely for each version (per-move time, total time for a game, extra memory) and contrasted with the O(n²) whole-board scan - The assumptions the O(1) state makes about the sequence of calls, and what happens when a caller violates them - A test plan with one case per outcome: a win on a row, a column, the main diagonal and the anti-diagonal, a draw, and an unfinished game ### Follow-up Questions - How would you add an `undo()` that reverts the last move in O(1) time? - Can you detect, still in O(1) per move, that a draw has become unavoidable because every row, column and diagonal already holds marks of both players, before the board is full? - If a win required only `k` consecutive marks in a line, with `k < n`, which parts of your design still work, and what would a move cost?