348. Design Tic-Tac-Toe

MediumDesignArrayHash TableMatrixSimulation

Problem Description

The given problem describes a tic-tac-toe game which is generalized for an n x n board, as opposed to the traditional 3 x 3 board. Two players take turns to place their mark on the board. The goal for each player is to get n of their own marks in a row, either horizontally, vertically, or diagonally. The challenge is to implement a class TicTacToe that can process each move made by the players and determine the status of the game after each move, specifically:

If the game continues with no winner.
If player 1 has won.
If player 2 has won.

Intuition

The main concept behind the solution is keeping track of the number of marks each player has in each row, column, and diagonal. We can achieve this by using an array or a list where each index represents the count of marks for a particular row, column, or diagonal. Each player has their own separate array of counts.

When a player makes a move, we increment the counts at the relevant indices, which correspond to the row and column of the move, and the two diagonals if applicable (when the move is on either of the diagonals). After updating the counts, we only need to check the counts of the current move's row, column, and possibly the diagonals. If any of these counts reach n, it signifies that n marks of the same player are aligned, and that player wins.

Specifically for diagonals, we can observe two properties:

The indices for the primary diagonal (row == col) are the same, so we can use a single counter for the entire diagonal.
The indices for the secondary diagonal (row + col == n - 1) also form a unique pattern, allowing us to use another single counter.

Let's create a two-dimensional list (or array) called counter, with two rows (one for each player) and 2n + 2 columns to cover all rows, all columns, and the two diagonals. We use player - 1 as the index to access the correct row in counter for the current player (since player ID is either 1 or 2, while list indexing starts from 0).

Every call to the move method updates these counts and checks for a win condition, returning 0 if there is no winner, 1 if player 1 wins, or 2 if player 2 wins. By only checking the counts related to the last move, we efficiently determine the outcome without re-scanning the entire board after every move.

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

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Solution Approach

The implementation of the TicTacToe class uses a methodical approach influenced by the need for efficiency in processing moves on an n x n tic-tac-toe board. The code consists of two primary components: the constructor __init__ and the method move.

In the __init__ method, we initialize two core elements:

self.n: Store the size of the board, which is used across the class to check for win conditions.
self.counter: A two-dimensional list (with dimensions 2x(2n + 2)) that holds the count of marks for both players across all rows, columns, and both diagonals. The rows represent each player (player 1 and player 2), while the columns represent the actual counts for each row, each column, and the two diagonals of the board. Note that we use a bit shift (n << 1) which is essentially doubling n, to determine the positions in the counter array where we track the diagonals.

The move method is the crux of the solution and is designed to handle a player's turn:

It increments the counts in self.counter for the current player by updating:
- The entry corresponding to the current row.
- The entry corresponding to the current col, offset by n to position it in the column-tracking part of the counter.
- If the move is on the primary diagonal (where row == col), we increment the entry at position n << 1.
- If the move is on the secondary diagonal (where row + col == n - 1), we increment the entry at position (n << 1) + 1.
After the move, the method checks if any of the counts (current row, column, or diagonals) have reached n. If so, we have a winner (the current player), and we return the player's number (1 or 2). If no winning condition is met, we return 0 to indicate that the game continues with no winner yet.

This solution uses the properties of a tic-tac-toe game board and simple arithmetic to keep track of potential winning conditions, which allows for constant time (O(1)) processing of each move regardless of the board size, making it highly efficient even as n increases.

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

Which technique can we use to find the middle of a linked list?

Fast-slow pointersTwo pointers moving in opposite directionBinary searchDepth first search

I don’t know

Example Walkthrough

Let's illustrate the solution approach with an example. Consider a 3x3 tic-tac-toe board, where n = 3. We want to simulate a few moves using the TicTacToe class to see how it tracks the game's status.

Initial Setup

We begin by initializing the game with n = 3, which will internally create a counter list with dimensions 2x(2*3 + 2) = 2x8. This counter will hold the count of marks for both players across all rows, columns, and both diagonals.

Process Moves

Suppose the following series of moves:

Player 1 places a mark at position (0, 0).
Player 2 places a mark at position (1, 1).
Player 1 places a mark at position (1, 0).
Player 2 places a mark at position (2, 2).
Player 1 places a mark at position (2, 0).

Turn-by-Turn Walkthrough

Now, let's walk through the moves one by one and see how the move method updates the counter and checks for a winner.

Turn 1: Player 1 (0, 0)
- Counter before move = [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- Move updates row 0 and column 0, and primary diagonal because it's the 0th position (row == col).
- Counter after move = [[1, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- No winner yet, so it returns 0.
Turn 2: Player 2 (1, 1)
- Counter before move = [[1, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- Move updates row 1 and column 1, and both diagonals because it's center of the board (row == col and row + col == n - 1).
- Counter after move = [[1, 0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- No winner yet, so it returns 0.
Turn 3: Player 1 (1, 0)
- Counter before move = [[1, 0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- Move updates row 1 and column 0 only.
- Counter after move = [[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- No winner yet, so it returns 0.
Turn 4: Player 2 (2, 2)
- Counter before move = [[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- Move updates row 2, column 2, and both diagonals since row + col == n - 1.
- Counter after move = [[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- No winner yet, so it returns 0.
Turn 5: Player 1 (2, 0)
- Counter before move = [[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- Move updates row 2, column 0, no diagonals aligned.
- Counter after move = [[1, 2, 0, 3, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- The counter for row 2 (third row of the board) has reached 3, which means Player 1 has n marks in a row and wins.
- It returns 1, indicating Player 1 wins.

After each move, only the scores in the counter that have been updated need to be checked. The returning value after the last move indicates if there is a winner or if the game continues.

Solution Implementation

1class TicTacToe:
2    def __init__(self, n: int):
3        """
4        Initialize the TicTacToe game board with a given size.
5        """
6        self.board_size = n
7        # self.counters store the counts for (rows, columns, diagonal, anti-diagonal)
8        # self.counters[player][i]: 
9        # i from 0 to n-1 (row counts), i from n to 2*n-1 (column counts),
10        # i equals 2*n (main diagonal count), i equals 2*n + 1 (anti-diagonal count)
11        # Index 0: player 1, Index 1: player 2
12        self.counters = [[0] * (2 * n + 2) for _ in range(2)]
13
14    def move(self, row: int, col: int, player: int) -> int:
15        """
16        Player makes a move at a specified row and column.
17        :param row: The row index of the board, 0-indexed.
18        :param col: The column index of the board, 0-indexed.
19        :param player: The identifier of the player (either 1 or 2).
20        :return: The current winning condition, can be either:
21                 0: No one wins.
22                 1: Player 1 wins.
23                 2: Player 2 wins.
24        """
25        player_index = player - 1  # Convert to 0-indexing for players 1 and 2
26        diagonal_index = 2 * self.board_size
27        anti_diagonal_index = 2 * self.board_size + 1
28
29        # Update the row, column, and possibly the diagonal counts for the move
30        self.counters[player_index][row] += 1  # Row count
31        self.counters[player_index][col + self.board_size] += 1  # Column count
32        if row == col:
33            self.counters[player_index][diagonal_index] += 1  # Diagonal count
34        if row + col == self.board_size - 1:
35            self.counters[player_index][anti_diagonal_index] += 1  # Anti-diagonal count
36
37        # Check if any count has reached the board size, which means a win.
38        if (
39            self.counters[player_index][row] == self.board_size
40            or self.counters[player_index][col + self.board_size] == self.board_size
41            or self.counters[player_index][diagonal_index] == self.board_size
42            or self.counters[player_index][anti_diagonal_index] == self.board_size
43        ):
44            return player  # The current player wins
45
46        # If no win, return 0 indicating no winner yet
47        return 0
48
49
50# Example of how the TicTacToe class is used:
51# game = TicTacToe(n)
52# result = game.move(row, col, player)
53

1public class TicTacToe {
2
3    private int size;  // Size of the board (n x n)
4    private int[][] moveCounters;  // Array to keep track of the count of moves for both players
5
6    /**
7     * Constructor to initialize the board of given size.
8     *
9     * @param n Size of the TicTacToe board.
10     */
11    public TicTacToe(int n) {
12        // Initialize counter for rows, columns, the main diagonal, and the anti-diagonal.
13        // For each player, we need n counters for rows, n for columns, one for the main diagonal,
14        // and one for the anti-diagonal.
15        moveCounters = new int[2][n * 2 + 2];  // 0 index for player 1 and 1 index for player 2
16        this.size = n;
17    }
18
19    /**
20     * Records a move by the player, checks the winning condition, and returns the game state.
21     *
22     * @param row    The row where the move is made.
23     * @param col    The column where the move is made.
24     * @param player The id of the player making the move, can be either 1 or 2.
25     * @return The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
26     */
27    public int move(int row, int col, int player) {
28        // Increment the corresponding row and column counters for the player.
29        moveCounters[player - 1][row]++;  // Increment row counter for the player
30        moveCounters[player - 1][col + size]++;  // Increment column counter for the player
31
32        // If the move is on the main diagonal, increment the main diagonal counter.
33        if (row == col) {
34            moveCounters[player - 1][size * 2]++;
35        }
36
37        // If the move is on the anti-diagonal, increment the anti-diagonal counter.
38        if (row + col == size - 1) {
39            moveCounters[player - 1][size * 2 + 1]++;
40        }
41
42        // Check each counter for the player to see if they've reached 'size';
43        // meaning they've filled a row, column, or diagonal.
44        if (moveCounters[player - 1][row] == size
45                || moveCounters[player - 1][col + size] == size
46                || moveCounters[player - 1][size * 2] == size
47                || moveCounters[player - 1][size * 2 + 1] == size) {
48            return player;  // The player has won the game.
49        }
50
51        return 0;  // No one has won the game yet.
52    }
53}
54
55/**
56 * Usage example:
57 * TicTacToe ticTacToe = new TicTacToe(3);
58 * int gameResult = ticTacToe.move(0, 0, 1);  // Move by player 1
59 * gameResult = ticTacToe.move(1, 1, 2);      // Move by player 2
60 * ... // Continues game play
61 */
62

1#include <vector>
2
3class TicTacToe {
4private:
5    int size;  // Size of the board (n x n)
6    std::vector<std::vector<int>> moveCounters;  // 2D vector to keep track of the count of moves for both players
7
8public:
9    /**
10     * Constructor to initialize the board of given size.
11     *
12     * @param n Size of the TicTacToe board.
13     */
14    TicTacToe(int n) : size(n), moveCounters(2, std::vector<int>(2 * n + 2, 0)) {
15        // The moveCounters vector keeps track of each player's move counts on rows, columns,
16        // main diagonal, and anti-diagonal.
17        // Index 0 for player 1 and 1 for player 2.
18        // The counts for rows are stored in [i][0 to n-1], for columns in [i][n to 2*n-1],
19        // main diagonal in [i][2*n], and anti-diagonal in [i][2*n + 1].
20    }
21
22    /**
23     * Records a move by the player, checks the winning condition and returns the game state.
24     *
25     * @param row    The row where the move is made.
26     * @param col    The column where the move is made.
27     * @param player The id of the player making the move, can be either 1 or 2.
28     * @return The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
29     */
30    int move(int row, int col, int player) {
31        int playerIndex = player - 1; // Adjust player id to index (0 or 1 for player 1 or 2 respectively)
32
33        // Increment the corresponding row and column counters for the player.
34        moveCounters[playerIndex][row]++;  // Increment row counter for the player
35        moveCounters[playerIndex][col + size]++;  // Increment column counter for the player
36
37        // If the move is on the main diagonal, increment the main diagonal counter.
38        if (row == col) {
39            moveCounters[playerIndex][size * 2]++;
40        }
41
42        // If the move is on the anti-diagonal, increment the anti-diagonal counter.
43        if (row + col == size - 1) {
44            moveCounters[playerIndex][size * 2 + 1]++;
45        }
46
47        // Check the counters for the player to see if they've reached 'size',
48        // which would mean they've filled a row, column, or diagonal.
49        if (moveCounters[playerIndex][row] == size 
50            || moveCounters[playerIndex][col + size] == size 
51            || moveCounters[playerIndex][size * 2] == size 
52            || moveCounters[playerIndex][size * 2 + 1] == size) {
53            return player;  // The player has won the game.
54        }
55
56        return 0;  // No one has won the game yet.
57    }
58};
59
60/**
61 * Usage example:
62 *
63 * TicTacToe ticTacToe(3);
64 * int gameResult = ticTacToe.move(0, 0, 1);  // Move by player 1
65 * gameResult = ticTacToe.move(1, 1, 2);      // Move by player 2
66 * ... // Continues game play
67 */
68

1// Size of the TicTacToe board (n x n).
2let size: number;
3
4// Array to keep track of the count of moves for both players.
5let moveCounters: number[][];
6
7// Initialize the board of given size.
8// n: Size of the TicTacToe board.
9function initializeGame(n: number): void {
10    // Initialize counter for rows, columns, the main diagonal, and the anti-diagonal.
11    // For each player, we need n counters for rows, n for columns, one for the main diagonal,
12    // and one for the anti-diagonal.
13    moveCounters = [[],[]]; // Index 0 for player 1 and index 1 for player 2 
14    for(let i = 0; i < 2; i++) { // Initialize all counters to zero.
15        for(let j = 0; j < n * 2 + 2; j++){
16            moveCounters[i][j] = 0;
17        }
18    }
19    size = n;
20}
21
22// Records a move by the player, checks the winning condition, and returns the game state.
23// row: The row where the move is made.
24// col: The column where the move is made.
25// player: The id of the player making the move, can be either 1 or 2.
26// Returns: The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
27function move(row: number, col: number, player: number): number {
28    // Increment the corresponding row and column counters for the player.
29    moveCounters[player - 1][row]++; // Increment row counter for the player
30    moveCounters[player - 1][col + size]++; // Increment column counter for the player
31
32    // If the move is on the main diagonal, increment the main diagonal counter.
33    if (row === col) {
34        moveCounters[player - 1][size * 2]++;
35    }
36
37    // If the move is on the anti-diagonal, increment the anti-diagonal counter.
38    if (row + col === size - 1) {
39        moveCounters[player - 1][size * 2 + 1]++;
40    }
41
42    // Check if any counter for the player has reached 'size' for a victory.
43    if (moveCounters[player - 1][row] === size ||
44        moveCounters[player - 1][col + size] === size ||
45        moveCounters[player - 1][size * 2] === size ||
46        moveCounters[player - 1][size * 2 + 1] === size) {
47        return player; // The player has won the game.
48    }
49
50    return 0; // No one has won the game yet.
51}
52
53// Usage example
54initializeGame(3); 
55let gameResult = move(0, 0, 1); // Move by player 1
56gameResult = move(1, 1, 2); // Move by player 2
57// ... Continue game play
58

Not Sure What to Study? Take the 2-min Quiz：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Time and Space Complexity

Time Complexity

The time complexity for the move method in the TicTacToe class is O(1). This is because the method executes a constant number of operations for any given move, regardless of the size of the board.

In each call to move, the method updates the corresponding counters for rows, columns, and diagonals based on the player's choice, which are direct accesses and increments in the self.counter 2D list. The checks for a win condition also involve constant-time comparisons since we are only checking if any row, column, or diagonal has reached the count n.

Space Complexity

The space complexity for the TicTacToe class is O(n). This complexity comes from the need to store counts for each row, each column, and the two diagonals.

There are 2n counters for rows and columns (since there are n of each, and each player has their own counters), plus an additional 2 counters for the two diagonals (again separate for each player). Therefore, the counter array has a size of 2 * (n + n + 2) which simplifies to 4n + 4. The additional 4 is a constant that does not impact the space complexity in terms of O notation, meaning the space usage is linear with respect to the size of the board.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

348. Design Tic-Tac-Toe

Problem Description

Intuition

Solution Approach

Example Walkthrough

Initial Setup

Process Moves

Turn-by-Turn Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity