1275. Find Winner on a Tic Tac Toe Game

EasyArrayHash TableMatrixSimulation
Leetcode Link

Problem Description

Tic-tac-toe is a classic game for two players, "A" and "B", played on a 3x3 grid. The objective is to be the first to get three of their own marks in a row either horizontally, vertically, or diagonally. In this LeetCode problem, we are given a list of moves where each move is represented by a pair of integers that correspond to a row and column on the grid. The task is to determine the outcome of the game based on the sequence of moves. The rules are as follows:

  • Player "A" uses the mark 'X' and makes the first move, while player "B" uses the mark 'O'.
  • Players alternate turns, placing their mark on an empty cell.
  • The game ends when a player has three of their marks in a row or all cells are filled.
  • If a player wins, their identity ("A" or "B") should be returned.
  • If all cells are filled without a winner, the game is a draw and "Draw" should be returned.
  • If the game has not ended, "Pending" should be returned.

The array moves represents the game sequence where moves[i] = [row_i, col_i] is the i-th move played on the grid at the cell defined by the row and column indices.

Intuition

The solution provided leverages a counting approach to keep track of the game's state without having to construct the entire grid after each move. Here's the intuition behind the solution:

  • We create a count array cnt of length 8 to keep track of marks along the rows, columns, and diagonals. The first three positions are for the rows, the next three positions for the columns, and the last two for the two diagonals.
  • We iterate over the moves inversely for both players, skipping moves alternatively (since players take turns).
  • Each player's move is analyzed with respect to the potential winning conditions: filling a row, column, or diagonal. We increment the respective counter for the move made.
  • After each move, we check if any counters have reached 3, indicating a winning condition.
  • If there's a winner, we identify which player's turn it was based on whether the number of moves made so far is odd or even, and return "A" or "B" accordingly.
  • If no winner is detected and the total moves made are 9, we declare the game a draw.
  • If the game is not won and not all moves are played, we return "Pending" indicating unfinished status.

This approach simplifies the problem by focusing only on the winning conditions without reconstructing the entire board for each move, which makes the solution more efficient.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

Solution Approach

Starting with the observation that a player wins if they achieve three of their symbols in a row, column, or diagonal, the code implements an elegant solution to identify the game's status after each move is made.

Here is a step-by-step approach to the implementation:

  1. Create a counter array cnt with 8 zeros, where cnt[0] to cnt[2] correspond to the three rows, cnt[3] to cnt[5] to the three columns, and cnt[6] and cnt[7] to the two diagonals of the board.

  2. Iterate over the moves in reverse order using the range range(n-1, -1, -2), where n is the length of the moves list. This iteration goes backwards and skips every other move to alternate between players A and B as they play.

  3. For each move, extract the row and column from moves[k]. Increment the respective counters in cnt for the row index i and column index j+3. This update simulates placing the 'X' or 'O' on the board.

  4. Check for a diagonal match by:

    • Incrementing cnt[6] (the counter for the left-to-right diagonal) if i == j.
    • Incrementing cnt[7] (the counter for the right-to-left diagonal) if i + j == 2.

  5. After updating the cnt, check if any value in cnt has reached 3 using the condition any(v == 3 for v in cnt). This check is indicative of a winning condition.

  6. If there is a winner, return "B" if k is odd (since the moves list includes player A's moves first, odd indexes will belong to player B during reverse iteration), or "A" if k is even, indicating it was player A's turn during the move that secured the win.

  7. If no winner is found and the total number of moves n is 9 (meaning every cell has been filled without achieving a winning condition), the game ends in a Draw, and so we return "Draw".

  8. In the final case where no winner is found and n is less than 9, not all cells have been filled, thus the game is still ongoing, and the code returns "Pending".

This method is efficient because it works incrementally, only tracking the essentials for determining the game outcome and not reconstructing the entire board's state after each move. It effectively makes use of a single-pass and counter-based technique, which is ideal for this array-based simulation of the tic-tac-toe game.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider an example game represented by the sequence of moves:

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

In this example, player A (using 'X') makes the first move at the top-left corner of the grid (0,0), followed by player B (using 'O') making a move at the bottom-left corner (2,0). The game proceeds with each player taking turns.

Now, let's walk through the moves according to the solution approach:

  1. We initialize a counter array cnt with 8 zeros: cnt = [0,0,0,0,0,0,0,0].

  2. The length of the moves list is 5, and we start iterating from the last move to the first move, skipping every other one to simulate the alternating turns:

    • For k = 4, which is the move [2,2] by player A:

      • The row index is 2, so we increment cnt[2].
      • The column index is 2, so we increment cnt[5].
      • Since the row and column indices are equal, indicating a diagonal, we increment cnt[6].

    • For k = 2, which is the move [1,1] by player A:

      • The row index is 1, so we increment cnt[1].
      • The column index is 1, so we increment cnt[4].
      • The indices are the same, indicating the diagonal again, so we increment cnt[6].

    At this point, after the even-indexed moves by player A, cnt looks like this: [0,1,1,0,1,1,2,0].

  3. Then we iterate for player B:

    • For k = 3, which is the move [2,1] by player B:
      • The row index is 2, so we increment cnt[2].
      • The column index is 1, so we increment cnt[4].

(Note: Player B does not contribute to diagonal counters in these moves.)

  1. After these iterations, we check if any counters reached the value of 3, which would indicate a win. Since none have, we proceed.

The current state of cnt is [0,1,2,0,2,1,2,0]. No values are 3, so no winner yet.

  1. Since only 5 moves are made and the total number of moves is less than 9, we cannot have a 'Draw', so we return 'Pending'.

As a result, the output for this sequence will be "Pending", as the game has not concluded yet.

Solution Implementation

1class Solution:
2    def tictactoe(self, moves):
3        # Initialize the number of moves
4        num_moves = len(moves)
5        # '\counters' is a list that holds the count of marks for each row, column and diagonals
6        # indexes [0,1,2] are for rows, [3,4,5] are for columns, [6] is for diagonal, [7] is for anti-diagonal
7        counters = [0] * 8
8
9        # Start from the last move and check if there is a winner after every move
10        for idx in range(num_moves - 1, -1, -2):
11            # Get the row and column index from the last move
12            row, col = moves[idx]
13          
14            # Increment the corresponding row and column counters
15            counters[row] += 1
16            counters[col + 3] += 1
17          
18            # If the move is on the main diagonal, increment the corresponding counter
19            if row == col:
20                counters[6] += 1
21          
22            # If the move is on the anti-diagonal, increment the corresponding counter
23            if row + col == 2:
24                counters[7] += 1
25          
26            # Check if any counters reached 3, which would indicate a win
27            if any(value == 3 for value in counters):
28                # Return 'B' if the current index is odd (indicating player "B"'s turn), otherwise 'A'
29                return "B" if idx % 2 else "A"
30      
31        # After all moves, if no winner is found, check if the board is full. If yes, it's a draw
32        # Otherwise, the game is still pending
33        return "Draw" if num_moves == 9 else "Pending"
34
1class Solution {
2    public String tictactoe(int[][] moves) {
3        int totalMoves = moves.length; // Total number of moves made.
4        int[] counts = new int[8]; // Array to keep track of the counts across rows, columns, and diagonals.
5      
6        // Iterate from the last move to the first, decrementing by 2 to alternate between players.
7        for (int moveIndex = totalMoves - 1; moveIndex >= 0; moveIndex -= 2) {
8            int row = moves[moveIndex][0]; // Row of the current move.
9            int col = moves[moveIndex][1]; // Column of the current move.
10          
11            // Increment the count for the current row and column.
12            counts[row]++;
13            counts[col + 3]++;
14          
15            // Check for diagonal win condition (top-left to bottom-right).
16            if (row == col) {
17                counts[6]++;
18            }
19          
20            // Check for anti-diagonal win condition (top-right to bottom-left).
21            if (row + col == 2) {
22                counts[7]++;
23            }
24          
25            // Check if the current player has won (if any count reaches 3).
26            if (counts[row] == 3 || counts[col + 3] == 3 || counts[6] == 3 || counts[7] == 3) {
27                return moveIndex % 2 == 0 ? "A" : "B"; // Return winner "A" or "B" based on move index.
28            }
29        }
30      
31        // If all 9 moves are made and no winner, it is a draw.
32        return totalMoves == 9 ? "Draw" : "Pending"; // If not a draw, the game is still pending.
33    }
34}
35
1class Solution {
2public:
3    string tictactoe(vector<vector<int>>& moves) {
4        int movesCount = moves.size(); // Total number of moves made
5
6        // Array to keep track of the count of marks for rows, columns, and diagonals
7        // Rows:    indices 0-2
8        // Columns: indices 3-5
9        // Diagonals: index 6 (left-top to right-bottom), index 7 (left-bottom to right-top)
10        int count[8] = {0};
11
12        // We start checking the game status from the last move backwards
13        for (int k = movesCount - 1; k >= 0; k -= 2) {
14            int row = moves[k][0];
15            int col = moves[k][1];
16
17            count[row]++; // Increment row count
18            count[col + 3]++; // Increment column count
19
20            // Check for diagonal - top-left to bottom-right
21            if (row == col) {
22                count[6]++;
23            }
24
25            // Check for anti-diagonal - bottom-left to top-right
26            if (row + col == 2) {
27                count[7]++;
28            }
29
30            // Check if player made 3 marks in a row, column, or diagonal
31            if (count[row] == 3 || count[col + 3] == 3 || count[6] == 3 || count[7] == 3) {
32                // If the index is even, it is player A's move; if odd, player B's move.
33                return k % 2 == 0 ? "A" : "B";
34            }
35        }
36
37        // If all 9 moves are made and no winner, it is a draw. Otherwise, game is pending.
38        return movesCount == 9 ? "Draw" : "Pending";
39    }
40};
41
1function tictactoe(moves: number[][]): string {
2    // Total number of moves made, corresponds to the number of turns played
3    const totalMoves = moves.length;
4  
5    // An array to count the moves for rows, columns, and diagonals
6    // Indices 0-2 for rows, 3-5 for columns, 6-7 for diagonals
7    const moveCounters = new Array(8).fill(0);
8  
9    // Iterate through the moves in reverse, starting with the last move
10    for (let moveIdx = totalMoves - 1; moveIdx >= 0; moveIdx -= 2) {
11        const [row, col] = moves[moveIdx];
12      
13        // Increment the counters for the current row and column
14        moveCounters[row]++;
15        moveCounters[col + 3]++;
16      
17        // If the move is on the main diagonal, increment the counter
18        if (row === col) {
19            moveCounters[6]++;
20        }
21      
22        // If the move is on the secondary diagonal, increment the counter
23        if (row + col === 2) {
24            moveCounters[7]++;
25        }
26      
27        // Check if any counter has reached 3, indicating a win
28        if (moveCounters[row] === 3 || moveCounters[col + 3] === 3 || moveCounters[6] === 3 || moveCounters[7] === 3) {
29            // Determine the winner based on the index of the move
30            return moveIdx % 2 === 0 ? 'A' : 'B';
31        }
32    }
33  
34    // If all 9 spaces were played and no winner, it's a draw
35    return totalMoves === 9 ? 'Draw' : 'Pending';
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Time and Space Complexity

The time complexity of the given code is O(1), as the function processes a fixed number (at most 9) of moves, regardless of the input size. The logic within the loop has a constant number of operations (checking the status of the game board, incrementing counters, and checking for a win condition), and thus does not grow with input size.

The space complexity of the code is also O(1) because the amount of memory used does not depend on the input size either. The cnt list has a constant size of 8, and no additional memory is allocated that would depend on the input.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫