Problem Description

This problem asks you to implement a Tic-Tac-Toe game for an n x n board that can determine the winner after each move.

You need to create a TicTacToe class with two methods:

• TicTacToe(int n): Initializes a game board of size n x n
• int move(int row, int col, int player): Places a mark for the given player (1 or 2) at position (row, col) and returns:
  • 0 if there's no winner yet
  • 1 if player 1 wins
  • 2 if player 2 wins

A player wins when they successfully place n of their marks in:

• Any complete row
• Any complete column
• The main diagonal (from top-left to bottom-right)
• The anti-diagonal (from top-right to bottom-left)

The solution uses a counting approach where it tracks how many marks each player has placed in each row, column, and diagonal. The key insight is to use a dictionary to count marks:

• Rows are indexed as 0 to n-1
• Columns are indexed as n to 2n-1
• Main diagonal is indexed as n << 1 (which is 2n)
• Anti-diagonal is indexed as n << 1 | 1 (which is 2n + 1)

For each move, the solution increments the appropriate counters for that player's row, column, and potentially diagonals (if the move is on a diagonal). If any counter reaches n, that player has won.

The main diagonal contains cells where row == col, and the anti-diagonal contains cells where row + col == n - 1. This clever indexing scheme allows checking for a win in O(1) time after each move.

Intuition

The key insight is that we don't need to store the entire board state to determine if someone has won. Instead, we only need to track how many marks each player has placed in each possible winning line.

Think about what constitutes a win in Tic-Tac-Toe: a player needs to fill an entire row, column, or diagonal with their marks. So rather than checking the entire board after each move, we can maintain counters for each possible winning line.

For an n x n board, there are exactly 2n + 2 possible winning lines:

• n rows
• n columns
• 1 main diagonal
• 1 anti-diagonal

The challenge is how to efficiently track and update these counters. We can assign a unique index to each winning line:

• Rows get indices 0 to n-1
• Columns get indices n to 2n-1
• The main diagonal gets index 2n (written as n << 1 using bit shift)
• The anti-diagonal gets index 2n + 1 (written as n << 1 | 1)

When a player makes a move at position (row, col), we know exactly which lines are affected:

• The row at index row
• The column at index n + col
• If row == col, the move is on the main diagonal
• If row + col == n - 1, the move is on the anti-diagonal

By incrementing the appropriate counters for the current player and checking if any counter has reached n, we can determine in constant time whether this move results in a win. This avoids the need to scan through rows, columns, or diagonals after each move, making the solution very efficient.

Solution Approach

The implementation uses a counting strategy with dictionaries to track the number of marks each player has placed in each winning line.

Data Structure:

• self.cnt: A list containing two dictionaries, one for each player. Each dictionary maps a line index to the count of marks that player has in that line.
• self.n: Stores the board size for easy reference.

Initialization (__init__):

self.cnt = [defaultdict(int), defaultdict(int)]

We create two defaultdict(int) objects, one for player 1 (at index 0) and one for player 2 (at index 1). Using defaultdict allows us to automatically initialize counts to 0 when accessing a new key.

Move Implementation (move):

1. First, we get the current player's counter dictionary:

   cur = self.cnt[player - 1]

   Since players are numbered 1 and 2, but list indices are 0-based, we use player - 1.

2. Update the row counter:

   cur[row] += 1

   The row index directly corresponds to the row number.

3. Update the column counter:

   cur[n + col] += 1

   Columns are offset by n to avoid collision with row indices.

4. Check and update diagonal counters:

   • Main diagonal (top-left to bottom-right):

     if row == col:
         cur[n << 1] += 1

     The main diagonal uses index 2n (written as n << 1 using left bit shift).

   • Anti-diagonal (top-right to bottom-left):

     if row + col == n - 1:
         cur[n << 1 | 1] += 1

     The anti-diagonal uses index 2n + 1 (written as n << 1 | 1 using bitwise OR).

5. Check for a win:

   if any(cur[i] == n for i in (row, n + col, n << 1, n << 1 | 1)):
       return player

   We check if any of the affected lines (current row, current column, and possibly diagonals) now have n marks. If so, the current player wins.

6. If no win is detected, return 0.

Time Complexity: O(1) per move - we only update and check a constant number of counters.

Space Complexity: O(n) - we store at most 2n + 2 counters for each player.

Example Walkthrough

Let's walk through a 3x3 Tic-Tac-Toe game to illustrate how the solution works.

Initial Setup:

• Board size n = 3
• Player 1's counter: cnt[0] = {}
• Player 2's counter: cnt[1] = {}
• Index mapping:
  • Rows: 0, 1, 2
  • Columns: 3, 4, 5
  • Main diagonal: 6 (n << 1)
  • Anti-diagonal: 7 (n << 1 | 1)

Move 1: Player 1 places at (0, 0)

X . .
. . .
. . .

• Update row 0: cnt[0][0] = 1
• Update column 0: cnt[0][3] = 1 (3 = n + 0)
• Cell (0,0) is on main diagonal (row == col), so: cnt[0][6] = 1
• Check counters: all are 1, no winner yet
• Return: 0

Move 2: Player 2 places at (1, 1)

X . .
. O .
. . .

• Update row 1: cnt[1][1] = 1
• Update column 1: cnt[1][4] = 1 (4 = n + 1)
• Cell (1,1) is on main diagonal (row == col), so: cnt[1][6] = 1
• Check counters: all are 1, no winner yet
• Return: 0

Move 3: Player 1 places at (0, 1)

X X .
. O .
. . .

• Update row 0: cnt[0][0] = 2 (was 1, now 2)
• Update column 1: cnt[0][4] = 1
• Cell (0,1) is not on any diagonal
• Check counters: row 0 has 2 marks, still need 3 to win
• Return: 0

Move 4: Player 2 places at (2, 0)

X X .
. O .
O . .

• Update row 2: cnt[1][2] = 1
• Update column 0: cnt[1][3] = 1
• Cell (2,0) is on anti-diagonal (2 + 0 = 2 = n - 1), so: cnt[1][7] = 1
• Check counters: all are 1, no winner yet
• Return: 0

Move 5: Player 1 places at (0, 2)

X X X
. O .
O . .

• Update row 0: cnt[0][0] = 3 (was 2, now 3)
• Update column 2: cnt[0][5] = 1
• Cell (0,2) is on anti-diagonal (0 + 2 = 2 = n - 1), so: cnt[0][7] = 1
• Check counters: row 0 has 3 marks = n, Player 1 wins!
• Return: 1

Final state of counters:

• Player 1: {0: 3, 3: 1, 6: 1, 4: 1, 5: 1, 7: 1}
  • Row 0 has 3 marks (winning line)
  • Column 0, main diagonal, column 1, column 2, anti-diagonal each have 1 mark
• Player 2: {1: 1, 4: 1, 6: 1, 2: 1, 3: 1, 7: 1}
  • All counters have only 1 mark

The key insight: instead of scanning the entire board, we only needed to check the counters for the lines affected by the current move. When Player 1's row 0 counter reached 3, we immediately knew they won.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) per move operation. Each move involves:

• Incrementing counters for the row (cur[row] += 1)
• Incrementing counters for the column (cur[n + col] += 1)
• Conditionally incrementing the diagonal counter (cur[n << 1] += 1)
• Conditionally incrementing the anti-diagonal counter (cur[n << 1 | 1] += 1)
• Checking at most 4 values to determine if there's a winner

All these operations take constant time regardless of the board size n.

Space Complexity: O(n) where n is the side length of the board. The space is used by:

• Two dictionaries (one for each player) in self.cnt
• Each dictionary can store at most 2n + 2 entries:
  • n entries for rows (keys 0 to n-1)
  • n entries for columns (keys n to 2n-1)
  • 1 entry for the main diagonal (key n << 1)
  • 1 entry for the anti-diagonal (key n << 1 | 1)

Since the number of possible keys is linear with respect to n, the overall space complexity is O(n).

Common Pitfalls

1. Incorrect Diagonal Check Logic

A frequent mistake is checking if a position is on a diagonal after already incrementing the counter, or using the wrong conditions for diagonal membership.

Pitfall Example:

# Wrong: Checking diagonals for every move
current_player_counts[n << 1] += 1  # Always incrementing
if row == col:  # Checking condition after increment
    # ...

Solution: Always check the diagonal condition BEFORE incrementing the counter:

if row == col:  # Check first
    current_player_counts[n << 1] += 1  # Then increment

2. Index Collision Between Rows and Columns

Without proper offset, row and column indices can overlap, causing incorrect win detection.

Pitfall Example:

# Wrong: Using same index range for rows and columns
current_player_counts[row] += 1
current_player_counts[col] += 1  # col could equal row for different lines!

Solution: Use distinct index ranges by offsetting column indices:

current_player_counts[row] += 1      # Rows: 0 to n-1
current_player_counts[n + col] += 1  # Columns: n to 2n-1

3. Checking All Lines Instead of Affected Lines

Checking every possible winning line after each move is inefficient and can lead to false positives if not careful.

Pitfall Example:

# Inefficient: Checking all possible lines
for i in range(n):
    if current_player_counts[i] == n:  # Checking all rows
        return player
for i in range(n, 2*n):
    if current_player_counts[i] == n:  # Checking all columns
        return player

Solution: Only check the lines affected by the current move:

lines_to_check = [row, n + col, n << 1, n << 1 | 1]
if any(current_player_counts[line_id] == n for line_id in lines_to_check):
    return player

4. Anti-Diagonal Condition Error

The anti-diagonal condition is often confused with the main diagonal or calculated incorrectly.

Pitfall Example:

# Wrong anti-diagonal conditions
if row == n - col:  # Incorrect formula
if row - col == n - 1:  # Also incorrect

Solution: The correct anti-diagonal condition is when the sum of row and column equals n-1:

if row + col == n - 1:  # Correct: top-right to bottom-left diagonal
    current_player_counts[n << 1 | 1] += 1

5. Player Index Mapping Error

Since players are numbered 1 and 2 but arrays are 0-indexed, off-by-one errors are common.

Pitfall Example:

# Wrong: Direct player index usage
current_player_counts = self.player_counts[player]  # Index out of bounds for player=2

Solution: Always subtract 1 from the player number to get the correct array index:

current_player_counts = self.player_counts[player - 1]  # Correct: maps 1->0, 2->1