How hard is LeetCode 348. Design Tic-Tac-Toe?

LeetCode 348. Design Tic-Tac-Toe is rated Medium on LeetCode.

What is the time complexity of LeetCode 348. Design Tic-Tac-Toe?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 348. Design Tic-Tac-Toe?

The Python solution on this page uses O(n), where n is the length of the side of the chessboard auxiliary space.

What topics does LeetCode 348. Design Tic-Tac-Toe cover?

LeetCode 348. Design Tic-Tac-Toe is tagged Design, Array, Hash Table, Matrix and Simulation on LeetCode.

Is LeetCode 348. Design Tic-Tac-Toe a premium problem?

Yes. LeetCode 348. Design Tic-Tac-Toe is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Design Tic-Tac-Toe — LeetCode 348 Python Solution

MediumLeetCode PremiumDesignArrayHash TableMatrixSimulation

Problem: #348
Pattern: Matrix and Grid
Reading time: 5 min
Source: leetcode.com

The problem

Assume the following rules are for the tic-tac-toe game on an n x n board between two players: A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves are allowed.

Example

Input: ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
Output: [null, 0, 0, 0, 0, 0, 0, 1]
Explanation: TicTacToe ticTacToe = new TicTacToe(3);

Python solution

Python

class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.cnt = [defaultdict(int), defaultdict(int)]

    def move(self, row: int, col: int, player: int) -> int:
        cur = self.cnt[player - 1]
        n = self.n
        cur[row] += 1
        cur[n + col] += 1
        if row == col:
            cur[n << 1] += 1
        if row + col == n - 1:
            cur[n << 1 | 1] += 1
        if any(cur[i] == n for i in (row, n + col, n << 1, n << 1 | 1)):
            return player
        return 0


# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the side of the chessboard auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 348. Design Tic-Tac-Toe is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 348. Design Tic-Tac-Toe?: LeetCode 348. Design Tic-Tac-Toe is rated Medium on LeetCode.
What is the time complexity of LeetCode 348. Design Tic-Tac-Toe?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 348. Design Tic-Tac-Toe?: The Python solution on this page uses O(n), where n is the length of the side of the chessboard auxiliary space.
What topics does LeetCode 348. Design Tic-Tac-Toe cover?: LeetCode 348. Design Tic-Tac-Toe is tagged Design, Array, Hash Table, Matrix and Simulation on LeetCode.
Is LeetCode 348. Design Tic-Tac-Toe a premium problem?: Yes. LeetCode 348. Design Tic-Tac-Toe is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.