1275. Find Winner on a Tic Tac Toe Game
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.8%
Problem Breakdown
The problem involves determining the winner of a Tic Tac Toe game given a sequence of moves made by two players, A and B. The input is an array moves where each element is a pair representing the row and column on the 3x3 grid where a player marks their character (‘X’ for player A and ‘O’ for player B). The output should be either “A” if player A wins, “B” if player B wins, “Draw” if all squares are filled without a winner, or “Pending” if there are still moves left to play.
Inputs:
moves: A list of lists where each sublist contains two integers representing the row and column indices on the 3x3 grid.
Outputs:
- A string indicating the result of the game (“A”, “B”, “Draw”, or “Pending”).
Implicit Constraints/Edge Cases:
- The input is guaranteed to be valid, meaning it follows the rules of Tic Tac Toe.
- Player A always starts first and alternates with player B.
- The grid is initially empty.
Intuition
The brute-force approach would involve simulating the game on a 3x3 grid by iterating through each move and checking for a winner after every move. However, this approach is inefficient in terms of space complexity because it requires maintaining an entire grid state.
A better approach involves keeping track of the number of ‘X’s and ‘O’s placed in each row, column, and diagonal. By doing so, we can determine if any player has achieved a winning condition without needing to store the entire grid. This reduces both time and space complexity.
Approach
-
Initialize Counters: Create two 3x3 arrays (
rowsandcols) to keep track of the number of ‘X’s and ‘O’s in each row and column, respectively. Additionally, maintain two variables (diagandanti_diag) to count the number of ‘X’s and ‘O’s on the main diagonal and anti-diagonal. -
Simulate Moves: Iterate through the list of moves. For each move:
- Determine whether it is made by player A or B.
- Update the corresponding row, column, and diagonal counters based on the move.
- Check if any counter reaches 3 (indicating a win for the current player).
-
Determine Result: After processing all moves:
- If a player has won, return “A” or “B”.
- If all 9 squares are filled without a winner, return “Draw”.
- Otherwise, return “Pending”.
Complexity Analysis
- Time Complexity: O(n), where n is the number of moves. We iterate through each move once.
- Space Complexity: O(1). We use fixed-size arrays to keep track of counts, which does not depend on the input size.
Solution
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
rows, cols = [0] * 3, [0] * 3
diag = anti_diag = 0
player = 'A'
for r, c in moves:
if player == 'A':
rows[r] += 1
cols[c] += 1
if r == c:
diag += 1
if r + c == 2:
anti_diag += 1
else:
rows[r] -= 1
cols[c] -= 1
if r == c:
diag -= 1
if r + c == 2:
anti_diag -= 1
# Check for a win condition
if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
return player
# Switch players
player = 'B' if player == 'A' else 'A'
# Check for a draw or pending game
return "Draw" if len(moves) == 9 else "Pending"
Edge Cases Handled
- Empty Input: The problem guarantees that the input is valid, so an empty input is not possible.
- All Moves Played Without a Winner: If all 9 moves are played and no player has won, the function returns “Draw”.
- Game Not Finished: If fewer than 9 moves are played and no player has won, the function returns “Pending”.