1275. Find Winner on a Tic Tac Toe Game - Detailed Explanation

Problem Statement

You are given a 2D integer array moves where each element is a pair [row, col] representing the position where a move is made on a 3x3 Tic Tac Toe board. The moves are played in order:

• The 1st move is made by player A
• The 2nd move is made by player B
• The players alternate thereafter

Your task is to determine the outcome of the game after all the moves have been played. The outcome should be:

• "A" if player A wins,
• "B" if player B wins,
• "Draw" if all 9 moves are played and neither player wins,
• "Pending" if the game is not yet finished (i.e. fewer than 9 moves have been played and there is no winner).

A player wins if they have three of their marks in a row (vertically, horizontally, or diagonally).

Hints

1. Winning Conditions:
   To determine if a player wins, you need to check:

   • Each of the 3 rows,
   • Each of the 3 columns,
   • The main diagonal (from top-left to bottom-right), and
   • The anti-diagonal (from top-right to bottom-left).

2. Optimized Check with Counters:
   Instead of building and scanning a full 3x3 board, you can maintain counters for rows, columns, and both diagonals.

   • When player A makes a move, add +1 to the relevant counters.
   • When player B makes a move, subtract 1.
   • If any counter reaches +3, then A wins; if any counter reaches –3, then B wins.

3. Game Outcome Determination:

   • If a winning condition is met during the moves, return the corresponding player immediately.
   • If no winner is found and all 9 moves are played, return "Draw".
   • If no winner is found and fewer than 9 moves have been played, return "Pending".

Approach: Counter-Based Method

Explanation

1. Initialize Counters:

   • Rows: An array of 3 integers, each representing the net score (A's count minus B's count) for that row.
   • Columns: An array of 3 integers for the columns.
   • Diagonal: A single integer for the main diagonal.
   • Anti-diagonal: A single integer for the anti-diagonal.

2. Process Each Move:

   • Iterate over the moves. For the (i)th move:
     • Determine the current player based on whether (i) is even (player A) or odd (player B).
     • For player A, add +1; for player B, add –1.
     • Update the counters for the row, column, and if applicable, the diagonal and anti-diagonal.
     • After each update, check if the absolute value of any counter reaches 3. If yes, declare the winner immediately (if the counter is +3, A wins; if –3, B wins).

3. Determine the Outcome:

   • If all moves are processed without any counter reaching 3:
     • If 9 moves were played, the game is a "Draw".
     • Otherwise, the game is "Pending".

Why This Works

• Efficiency:
  You only process each move once (O(1) per move) with constant-time updates and checks. Since there are at most 9 moves, the solution is very efficient.

• Correctness:
  Using counters effectively aggregates the contribution of each move in a way that if one player controls an entire row, column, or diagonal, the corresponding counter will reach +3 (or –3 for player B).

Code Solutions

Python Code