Problem Description

This problem asks you to determine the outcome of a Tic-tac-toe game given a sequence of moves.

In Tic-tac-toe:

• Two players A and B take turns on a 3×3 grid
• Player A always goes first and places 'X' characters
• Player B always places 'O' characters
• Players can only place their marks in empty squares
• A player wins by getting 3 of their marks in a row (horizontally, vertically, or diagonally)
• The game ends when someone wins or all 9 squares are filled

You're given a 2D array moves where moves[i] = [row_i, col_i] represents the i-th move in the game. The moves alternate between players - moves[0] is player A's first move, moves[1] is player B's first move, moves[2] is player A's second move, and so on.

Your task is to return:

• "A" if player A wins
• "B" if player B wins
• "Draw" if all 9 squares are filled with no winner
• "Pending" if the game hasn't ended yet (there are still empty squares and no winner)

The solution cleverly checks only if the last player to move has won, since the moves are guaranteed to be valid (no one would continue playing after someone already won). It tracks the count of marks in each row, column, and diagonal. If any count reaches 3, that player wins. The solution iterates backwards through moves in steps of 2 to check only the last player's moves, using an array cnt to track:

• cnt[0-2]: counts for rows 0, 1, 2
• cnt[3-5]: counts for columns 0, 1, 2
• cnt[6]: count for main diagonal (where i == j)
• cnt[7]: count for anti-diagonal (where i + j == 2)

Intuition

The key insight is that since all moves are valid (meaning no one continues playing after someone has already won), we only need to check if the most recent player has won the game. This dramatically simplifies our approach.

Think about it this way: if player A won on their 3rd move, player B wouldn't have made another move. So if we have a list of moves, and someone has won, it must be the player who made the last move.

Instead of simulating the entire board state, we can work backwards from the last move. We only need to check the positions occupied by the last player who moved. If they have 3 marks in any row, column, or diagonal, they've won.

To track this efficiently, we can use a counting approach. We create an array of 8 counters:

• 3 counters for the 3 rows
• 3 counters for the 3 columns
• 1 counter for the main diagonal (top-left to bottom-right)
• 1 counter for the anti-diagonal (top-right to bottom-left)

By iterating through only the last player's moves (going backwards in steps of 2), we increment the appropriate counters. A cell at position (i, j) contributes to:

• Row counter i
• Column counter j + 3 (offset by 3 to avoid overlap with row counters)
• Main diagonal counter (index 6) if i == j
• Anti-diagonal counter (index 7) if i + j == 2

If any counter reaches 3, that player has won. The player is determined by checking if the move index is odd or even - even indices belong to player A, odd indices to player B.

If no one has won after checking all moves, we simply check if all 9 squares are filled (n == 9) to determine if it's a draw or the game is still pending.

Solution Approach

The solution implements the counting strategy to determine if the last player to move has won the game.

Step 1: Initialize the counter array We create an array cnt of length 8 to track moves:

• cnt[0], cnt[1], cnt[2] - count moves in rows 0, 1, 2
• cnt[3], cnt[4], cnt[5] - count moves in columns 0, 1, 2
• cnt[6] - count moves on the main diagonal
• cnt[7] - count moves on the anti-diagonal

Step 2: Iterate through the last player's moves We start from the last move and go backwards in steps of 2 (range(n-1, -1, -2)). This ensures we only check moves made by the last player who moved.

Step 3: Update counters for each move For each move at position (i, j):

• Increment row counter: cnt[i] += 1
• Increment column counter: cnt[j + 3] += 1 (offset by 3 to separate from row counters)
• If on main diagonal (i == j): increment cnt[6] += 1
• If on anti-diagonal (i + j == 2): increment cnt[7] += 1

Step 4: Check for a winner After updating counters for each move, we check if any counter equals 3 using any(v == 3 for v in cnt). If true, the last player has won.

• If the move index k is odd (k & 1), player B wins (since B makes odd-indexed moves)
• Otherwise, player A wins

Step 5: Determine game status if no winner If we've checked all the last player's moves and found no winner:

• If n == 9 (all squares filled), return "Draw"
• Otherwise, return "Pending" (game still in progress)

The time complexity is O(n) where n is the number of moves, and space complexity is O(1) since we only use a fixed-size array of 8 elements.

Example Walkthrough

Let's walk through an example where moves = [[0,0], [1,1], [0,1], [2,2], [0,2]].

This represents the following game sequence:

• Move 0: Player A places X at (0,0)
• Move 1: Player B places O at (1,1)
• Move 2: Player A places X at (0,1)
• Move 3: Player B places O at (2,2)
• Move 4: Player A places X at (0,2)

The board after all moves looks like:

X X X
. O .
. . O

Step 1: Initialize

• n = 5 (total moves)
• cnt = [0, 0, 0, 0, 0, 0, 0, 0] (8 counters for rows, columns, diagonals)

Step 2: Check last player's moves Since we have 5 moves (odd number), the last move was made by player A. We'll check moves at indices 4, 2, and 0 (going backwards by 2).

Move at index 4: [0,2]

• Position (0,2): row=0, col=2
• Update counters:
  • cnt[0] += 1 → cnt = [1, 0, 0, 0, 0, 0, 0, 0] (row 0)
  • cnt[2+3] += 1 → cnt = [1, 0, 0, 0, 0, 1, 0, 0] (column 2)
  • Not on main diagonal (0 ≠ 2)
  • On anti-diagonal (0+2 = 2): cnt[7] += 1 → cnt = [1, 0, 0, 0, 0, 1, 0, 1]
• Check if any counter equals 3: No

Move at index 2: [0,1]

• Position (0,1): row=0, col=1
• Update counters:
  • cnt[0] += 1 → cnt = [2, 0, 0, 0, 0, 1, 0, 1] (row 0)
  • cnt[1+3] += 1 → cnt = [2, 0, 0, 0, 1, 1, 0, 1] (column 1)
  • Not on main diagonal (0 ≠ 1)
  • Not on anti-diagonal (0+1 ≠ 2)
• Check if any counter equals 3: No

Move at index 0: [0,0]

• Position (0,0): row=0, col=0
• Update counters:
  • cnt[0] += 1 → cnt = [3, 0, 0, 0, 1, 1, 0, 1] (row 0)
  • cnt[0+3] += 1 → cnt = [3, 0, 0, 1, 1, 1, 0, 1] (column 0)
  • On main diagonal (0 = 0): cnt[6] += 1 → cnt = [3, 0, 0, 1, 1, 1, 1, 1]
  • Not on anti-diagonal (0+0 ≠ 2)
• Check if any counter equals 3: Yes! cnt[0] == 3

Step 3: Determine winner Since we found a counter equal to 3 and the move index (0) is even, player A wins.

Result: "A"

The algorithm correctly identifies that player A won by getting three X's in row 0, without needing to simulate the entire board or check player B's positions.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of moves. The algorithm iterates through the moves array once in reverse order (from index n-1 to 0 with step -2), performing constant-time operations for each move. Even though we only process every other move (due to step -2), this still results in O(n) iterations in the worst case. Within each iteration, we perform a fixed number of operations: updating counters, checking conditions, and the any() function which checks at most 8 values (constant time).

The space complexity is O(1), not O(n) as stated in the reference answer. The algorithm uses a fixed-size array cnt of length 8 to track the state of rows, columns, and diagonals. This array size is constant and does not depend on the input size n. The only other variables used are loop counters and temporary variables (i, j, k), which also require constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Checking Both Players' Moves

A common mistake is checking all moves sequentially instead of only the last player's moves. Since we only need to know if someone has won (not predict future wins), we should only check if the player who just moved has achieved a winning condition.

Incorrect approach:

# Wrong: Checking all moves mixed together
for i in range(len(moves)):
    row, col = moves[i]
    win_conditions[row] += 1
    # This mixes both players' moves in the same counters!

Correct approach:

# Right: Only check the last player's moves
for move_index in range(len(moves) - 1, -1, -2):
    row, col = moves[move_index]
    # Now we're only counting one player's moves

2. Forgetting to Reset Counters Between Players

If you decide to check both players separately, forgetting to reset the counters between checking player A and player B will lead to incorrect results.

Incorrect approach:

# Wrong: Using same counters for both players
cnt = [0] * 8
# Check player A
for i in range(0, len(moves), 2):
    # update cnt...
  
# Check player B without resetting!
for i in range(1, len(moves), 2):
    # cnt still has player A's counts!

Correct approach:

# Reset counters or use separate arrays for each player
cnt_a = [0] * 8
cnt_b = [0] * 8

3. Anti-diagonal Condition Error

The anti-diagonal condition is row + col == 2 for a 3×3 board, not other formulas like row == 2 - col or abs(row - col) == 2.

Incorrect:

# Wrong anti-diagonal checks
if row == 2 - col:  # This works but less intuitive
if abs(row - col) == 2:  # This is wrong!

Correct:

# Correct anti-diagonal check
if row + col == 2:
    win_conditions[7] += 1

4. Misunderstanding Move Index and Player Mapping

The move index determines which player made the move. Even indices (0, 2, 4, 6, 8) are player A's moves, odd indices (1, 3, 5, 7) are player B's moves.

Incorrect:

# Wrong: Confusing the last move index with player
if len(moves) % 2 == 0:
    return "A"  # Wrong! This checks total moves, not who made the last move

Correct:

# Right: Check the actual move index
if move_index & 1:  # or move_index % 2 == 1
    return "B"
else:
    return "A"

5. Not Handling Edge Cases Properly

Remember that the game can end in multiple states, and checking only for a full board isn't sufficient.

Incorrect:

# Wrong: Only checking if board is full
if len(moves) == 9:
    return "Draw"
return "Pending"

Correct:

# Right: First check for winner, then distinguish between Draw and Pending
# After checking for winners...
return "Draw" if len(moves) == 9 else "Pending"