MediumNo. 0348LeetCode Premium
Design Tic-Tac-Toe — LeetCode 348 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Design, Array, Hash Table, Matrix, Simulation
- 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
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
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the length of the side of the chessboard
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1275 | Find Winner on a Tic Tac Toe Game | Easy |
| 2043 | Simple Bank System | Medium |
| 2352 | Equal Row and Column Pairs | Medium |
| 2502 | Design Memory Allocator | Medium |
| 0036 | Valid Sudoku | Medium |
| 0037 | Sudoku Solver | Hard |
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.