#1275

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Winner on a Tic Tac Toe Game

Determine the winner of a Tic Tac Toe game by scanning moves and using hash lookups for rows, columns, and diagonals efficiently.

array hash table matrix simulation

Problem Statement

Tic Tac Toe is played on a 3x3 grid by two players, A and B. Player A always starts first. Players alternate placing their marks on empty cells. A player wins if they fill an entire row, column, or diagonal with their mark. If all cells are filled without a winner, the game is a draw.

Given a list of moves where moves[i] = [rowi, coli] represents the position of the ith move, write a function to determine the game's result. Return "A" if player A wins, "B" if player B wins, "Draw" if the game ends with no winner, or "Pending" if there are moves left to play. Assume all moves are valid and follow Tic Tac Toe rules.

Examples

Example 1

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

Output: "A"

A wins, they always play first.

Example 2

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

Output: "B"

B wins.

Example 3

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

Output: "Draw"

The game ends in a draw since there are no moves to make.

Constraints

1 <= moves.length <= 9
moves[i].length == 2
0 <= rowi, coli <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Solution Approach

Track rows, columns, and diagonals with hash tables

Use separate hash tables for each player to count the number of their marks in each row, column, and the two diagonals. Increment counts for each move, and check if any count reaches three to immediately identify the winner.

Alternate players while scanning moves

Iterate through the moves array, assigning moves alternately to players A and B. Update the hash tables accordingly, ensuring that the pattern of filling a row, column, or diagonal is tracked correctly for each player.

Return game outcome efficiently

After processing all moves, if a player has three in any tracked line, return their winner symbol. If the moves fill the grid without a winner, return 'Draw'. Otherwise, return 'Pending'. This avoids full grid scanning at every step.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the number of moves, since each move updates at most five counters. Space complexity is O(1) with fixed-size arrays or hash tables for rows, columns, and diagonals, independent of the number of moves.

What Interviewers Usually Probe

Expecting recognition of array scanning combined with hash lookup pattern.
May probe edge cases like immediate diagonal or row wins.
Check whether candidate handles 'Pending' vs 'Draw' correctly.

Common Pitfalls or Variants

Common pitfalls

Failing to track diagonals separately, causing missed wins.
Swapping players incorrectly and assigning moves to the wrong hash table.
Checking the winner only at the end instead of after each move, missing early wins.

Follow-up variants

Larger grids such as NxN Tic Tac Toe, requiring scalable row, column, and diagonal tracking.
Tracking multiple simultaneous games in parallel, using hash tables per board.
Modifying the game rules to win with k consecutive marks instead of three.

FAQ

How do I determine the winner efficiently in 'Find Winner on a Tic Tac Toe Game'?

Use hash tables or arrays to count each player's marks in every row, column, and diagonal, checking after each move for three in a line.

What is the best data structure to track the game state?

Fixed-size arrays or hash tables are ideal, since you only need counters for three rows, three columns, and two diagonals.

How do I handle a game that ends without a winner?

After all moves are processed, if no player has three in a line and the grid is full, return 'Draw'; otherwise, return 'Pending'.

Can this solution scale for larger Tic Tac Toe grids?

Yes, by maintaining counts for each row, column, and diagonal, the same array scanning plus hash lookup pattern applies for NxN boards.

What common mistakes should I avoid?

Do not mix up player moves, forget diagonal tracking, or delay winner checking until all moves are scanned.

terminal

Solution

Solution 1: Determine if the last player to move can win

Since all `moves` are valid, that is, there is no situation where a person continues to play after someone has won. Therefore, we only need to determine whether the last player to move can win.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        n = len(moves)
        cnt = [0] * 8
        for k in range(n - 1, -1, -2):
            i, j = moves[k]
            cnt[i] += 1
            cnt[j + 3] += 1
            if i == j:
                cnt[6] += 1
            if i + j == 2:
                cnt[7] += 1
            if any(v == 3 for v in cnt):
                return "B" if k & 1 else "A"
        return "Draw" if n == 9 else "Pending"

Continue Practicing

#1284 minimum number of flips to convert binary matrix to zero matrix #1260 shift 2d grid #1222 queens that can attack the king