#### Problem Statement:

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 board n.
int move(int row, int col, int player): Indicates that player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Example:
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|

#### Solution:

This is a very simple yet interesting problem. While solutioning for this problem we would focus on how we go on optimizing our solution from O(n2) to all the way to O(1).

#### Brute Force O(n2) Algorithm:

The brute force approach to solve this problem is to iterate over the entire board of size n * n and check if the current player has marked any row, column, diagonal or anti-diagonal.

This approach is exhaustive and requires O(n2) time every time
move(int row, int col, int player)
method is called. Let's look at other more efficient approaches to solve the problem.

#### O(n) Algorithm:

Every time a player makes a move in a cell [x, y] we check the diagonal, the anti-diagonal and all the cells in the row with index x and all the cells in the column with index y to see if the player has won. Let's look at the code below:

class TicTacToe {

int[][] grid;

/** Initialize your data structure here. */
public TicTacToe(int n) {
grid = new int[n][n];
}

/** 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. */
public int move(int row, int col, int player) { // O(n)
if (row >= grid.length || col >= grid.length) { // out of the grid
return 0;
}

grid[row][col] = player == 1 ? 1 : 2; // make the move
// for player 1 we put 1 and for player 2 we put 2

if (checkVerticalWin(col, player)) { // did the player win vertically ?
return player;
}
if (checkHorizontalWin(row, player)) { // did the player win horizontally ?
return player;
}
if (checkDiagonalWin(row, col, player)) { // did the player win diagonally ?
return player;
}
if (checkAntiDiagonalWin(row, col, player)) { // did the player win anti-diagonally ?
return player;
}

return 0;
}

private boolean checkVerticalWin(int col, int player) { // Time Complexity: O(n) where dimension of the board is n X n.
for (int i = 0; i < grid.length; i++) {
if (grid[i][col] != player) {
return false;
}
}
return true;
}

private boolean checkHorizontalWin(int row, int player) { // Time Complexity: O(n) where dimension of the board is n X n.
for (int j = 0; j < grid.length; j++) {
if (grid[row][j] != player) {
return false;
}
}
return true;
}

private boolean checkDiagonalWin(int row, int col, int player) { // Time Complexity: O(n) where dimension of the board is n X n.
// Important observation:
// For a cell to be a diagonal cell in a tic-tac-toe board
// column coordinate needs to be same as row coordinate.
// In a 3 X 3 board diagonal cells are [0,0], [1,1], [2,2].
if (row != col) {
return false;
}
boolean topLeftToBottomRight = true;
for (int i = 0; i < grid.length; i++) {
if (grid[i][i] != player) {
topLeftToBottomRight = false;
}
}
}

private boolean checkAntiDiagonalWin(int row, int col, int player) { // Time Complexity: O(n) where dimansion of the board is n X n.
// Important observation:
// Let's take a look at all the anti-diagonal cells
// in a 3 X 3 tic-tac-toe board: [0,2], [1,1], [2,0]
// What is the common things among all the anti-diagonal
// cells coordinates: Look how for all of them
// row + col = 2 = 3 - 1.
// 0 + 2 = 2. 1 + 1 = 2. 2 + 0 = 2.
// So for a cell to be an anti-diagonal cell: col + row = length(tic-tac-toe board) - 1
if (row + col != grid.length-1) {
return false;
}
boolean topRightToBottomLeft = true;
for (int columnIndex = 0; columnIndex < grid.length; columnIndex++) {
int rowIndex = grid.length - 1 - columnIndex; // for anti-diagonal columnIndex + rowIndex = dimension of board - 1
if (grid[columnIndex][rowIndex] != player) {
topRightToBottomLeft = false;
}
}
}
}

/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/

Look how well-written and readable the above code is. Instead of putting everything in the
move(int row, int col, int player)
method how we have broken it down into multiple single-responsibility methods:
checkVerticalWin(int col, int player)

checkHorizontalWin(int row, int player)

checkDiagonalWin(int row, int col, int player)

checkAntiDiagonalWin(int row, int col, int player)

This makes the code highly maintainable. This is how a Clean Code looks like.

Whether you are preparing for technical interviews or trying to be a better software engineer or both, please always make it a priority to write clean code, a code that would take pride on. Even during an interview when you are tight on time please, please make it a priority to always write clean, readable and maintainable code. ] There should be no compromise on code quality at any circumstances.

The above code is O(n) where n is the dimension of the given tic-tac-toe board. Can we do better ? Yes! Take a look at the below algorithm.

#### O(1) Algorithm:

We land our most optimized solution by using some simple observations.

In the solution above whenever player 1 was making a move on a board cell we were putting 1 in that cell. Now just think what would we get when player 1 wins after making a move. Either one row or column or diagonal or anti-diagonal would have all 1's, which means the summation of the value in a row or column or diagonal or anti-diagonal would be equal to the dimension of the given tic-tac-toe board.

If we make a little change to our solution above and instead of putting 2 for player 2 if we put -1, then for the player 2 to win after making a move we would have the summation of values in all the cells in a row or column or diagonal or anti-diagonal equal to negative dimension i.e -n where dimension of board is n X n.

We implement the below solution based on the above discussed algorithm:

class TicTacToe {

int[] rowSum;
int[] colSum;
int diagonalSum;
int antiDiagonalSum;
int dimension;

/** Initialize your data structure here. */
public TicTacToe(int n) {
rowSum = new int[n];
colSum = new int[n];
diagonalSum = 0;
antiDiagonalSum = 0;
dimension = n;
}

/** 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. */
public int move(int row, int col, int player) {
int value = player == 1 ? 1 : -1;

rowSum[row] += value; // update the rowSum value
colSum[col] += value; // update the colSum value

if (row == col) { // if row == col then that would mean that this cell is on the diagonal
diagonalSum += value;
}

if (col == dimension - row - 1) { // the [row, col] cell is located on anti-diagonal
antiDiagonalSum += value;
}

// for the player to win by making this move
// summation of all values in the cells at row index = row must be equal to the dimension
// or
// summation of all values in the cells at column index = col must be equal to the dimension
// or
// summation of all values in the cells located on the diagonal must be equal to the dimension
// or
// summation of all values in the cells located on the anti-diagonal must be equal to the dimension
if (Math.abs(rowSum[row]) == dimension // row summation
|| Math.abs(colSum[col]) == dimension // column summation
|| Math.abs(diagonalSum) == dimension // diagonal summation
|| Math.abs(antiDiagonalSum) == dimension) { // anti-diagonal summation
return player;
}

return 0;

}
}

/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/