Tag
: Design
Matrix
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.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe
class:
TicTacToe(int n)
Initializes the object the size of the boardn
.int move(int row, int col, int player)
Indicates that the player with idplayer
plays at the cell(row, col)
of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return0
if there is no winner after the move,1
if player 1 is the winner after the move, or2
if player 2 is the winner after the move.
Example 1:
Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]
Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Constraints:
2 <= n <= 100
player
is1
or2
.0 <= row, col < n
(row, col)
are unique for each different call tomove
.- At most
n^2
calls will be made tomove
.
Follow-up: Could you do better than O(n^2)
per move()
operation?
-
Time Complexity:
$O(n)$ -
Space Complexity:
$O(n^2)$
class TicTacToe:
def __init__(self, n: int):
self.board = [[None] * n for _ in range(n)]
self.ROWS, self.COLS = n, n
def move(self, row: int, col: int, player: int) -> int:
if player == 1:
self.board[row][col] = 'O'
else:
self.board[row][col] = 'X'
def check_row(row, col):
for c in range(self.COLS):
if self.board[row][c] != self.board[row][col]:
return False
return True
def check_col(row, col):
for r in range(self.ROWS):
if self.board[r][col] != self.board[row][col]:
return False
return True
def check_diagonal(row, col):
for r in range(self.ROWS):
if self.board[r][r] != self.board[row][col]:
return False
return True
def check_anti_diagonal(row, col):
for r in range(self.ROWS):
if self.board[r][self.ROWS - r - 1] != self.board[row][col]:
return False
return True
if check_row(row, col) or check_col(row, col) or check_diagonal(row, col) or check_anti_diagonal(row, col):
return player
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
class TicTacToe:
def __init__(self, n: int):
self.board = [[None] * n for _ in range(n)]
self.ROWS, self.COLS = n, n
def move(self, row: int, col: int, player: int) -> int:
self.board[row][col] = player
def check_row(row, player):
for c in range(self.COLS):
if self.board[row][c] != player:
return False
return True
def check_col(col, player):
for r in range(self.ROWS):
if self.board[r][col] != player:
return False
return True
def check_diagonal(player):
for r in range(self.ROWS):
if self.board[r][r] != player:
return False
return True
def check_anti_diagonal(player):
for r in range(self.ROWS):
if self.board[r][self.ROWS - r - 1] != player:
return False
return True
if check_row(row, player) or check_col(col, player) or check_diagonal(player) or check_anti_diagonal(player):
return player
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
-
Time Complexity:
$O(1)$ -
Space Complexity:
$O(n)$
class TicTacToe:
def __init__(self, n: int):
self.player1 = {'row': collections.defaultdict(int), 'col':collections.defaultdict(int), 'diagonal':0, 'anti_diagonal':0}
self.player2 = {'row': collections.defaultdict(int), 'col':collections.defaultdict(int), 'diagonal':0, 'anti_diagonal':0}
self.size = n
def move(self, row: int, col: int, player: int) -> int:
if player == 1:
current = self.player1
else:
current = self.player2
current['row'][row] += 1
current['col'][col] += 1
if row == col:
current['diagonal'] += 1
if row + col == self.size - 1:
current['anti_diagonal'] += 1
if current['row'][row] == self.size or current['col'][col] == self.size or current['diagonal'] == self.size or current['anti_diagonal'] == self.size:
return player
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
class TicTacToe:
def __init__(self, n: int):
self.size = n
self.horizontal = [0] * n
self.vertical = [0] * n
self.diagonal = 0
self.anti_diagonal = 0
def move(self, row: int, col: int, player: int) -> int:
if player == 1:
move = 1
else:
move = -1
self.horizontal[col] += move
self.vertical[row] += move
if row == col:
self.diagonal += move
if row + col == self.size - 1:
self.anti_diagonal += move
if abs(self.horizontal[col]) == self.size or abs(self.vertical[row]) == self.size or abs(self.diagonal) == self.size or abs(self.anti_diagonal) == self.size:
return player
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)