**Solution**

**Design Tic-Tac-Toe** https://leetcode.com/problems/design-tic-tac-toe/

**Brute Force Solution**

- There are four strikes that can win for you. Row, Col, Diagonal, Anti-Diagonal.
- Diagonal: row == col. Anti-Diagonal: row+col=self.n-1. Use this condition to check diagonal and anti-diagonal.
- O(N) solution: At every move, test each strike if they have the same player. This will be like 4 times N.

```
class TicTacToe(object):
def __init__(self, n):
"""
Initialize your data structure here.
:type n: int
"""
self.board = [[-1]*n for _ in range(n)]
self.n = n
def move(self, row, col, player):
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
:type row: int
:type col: int
:type player: int
:rtype: int
"""
self.board[row][col] = player
col_check = row_check = diagonal_check = anti_diagonal_check = True
for j in range(self.n):
if self.board[row][j] != player:
col_check = False
break
if col_check:
return player
for i in range(self.n):
if self.board[i][col] != player:
row_check = False
break
if row_check:
return player
if row == col:
for k in range(self.n):
if self.board[k][k] != player:
diagonal_check = False
break
if diagonal_check:
return player
if row + col == self.n-1:
r,c = 0, self.n-1
for k in range(self.n):
if self.board[r][c] != player:
anti_diagonal_check = False
break
r,c = r+1,c-1
if anti_diagonal_check:
return player
return 0
```

**Optimized Solution**

- O(1) solution: Keep 2 arrays nrow and ncol. Keep 2 variables diagonal and anti_diagonal.
- nrow[i] = [player_index, count] and similarly ncol[i] = [player_index, count]. At each move, there is a win with respect to row if the current player is row[i,0] and its previous count is N-1. Similarly, we can derive a condition for col win.
- if row == col, then we test the diagonal variable whether it stored the current player and whether its previous count was N-1.
- if row+col =N-1, then we check the anti-diagonal.

```
class TicTacToe(object):
def __init__(self, n):
"""
Initialize your data structure here.
:type n: int
"""
self.row, self.col = [None]*n, [None]*n
self.diagonal, self.anti_diagonal = None, None
self.n = n
def move(self, row, col, player):
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
:type row: int
:type col: int
:type player: int
:rtype: int
"""
diagonal_check = anti_diagnoal = True
if self.row[row] == None:
self.row[row] = [player, 1]
elif self.row[row][0] == player:
if self.row[row][1] == self.n-1:
return player
else:
self.row[row][1] = self.row[row][1] + 1
if self.col[col] == None:
self.col[col] = [player, 1]
elif self.col[col][0] == player:
if self.col[col][1] == self.n-1:
return player
else:
self.col[col][1] = self.col[col][1] + 1
if row == col:
if self.diagonal == None:
self.diagonal = [player, 1]
elif self.diagonal[0] == player:
if self.diagonal[1] == self.n-1:
return player
else:
self.diagonal[1] = self.diagonal[1] + 1
if row + col == self.n-1:
if self.anti_diagonal == None:
self.anti_diagonal = [player, 1]
elif self.anti_diagonal[0] == player:
if self.anti_diagonal[1] == self.n-1:
return player
else:
self.anti_diagonal[1] = self.anti_diagonal[1] + 1
return 0
```

Also check this brilliant solution: https://discuss.leetcode.com/topic/44548/java-o-1-solution-easy-to-understand/2