TicTacToe

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 Click here to access our Premium Algorithms course.
Problem Statement:
Assume the following rules are for the tictactoe 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 OO  // Player 2 makes a move at (1, 0). X X ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) X O OO  // Player 1 makes a move at (2, 1). XXX
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(n^{2}) to all the way to O(1).Brute Force O(n^{2}) 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 antidiagonal.This approach is exhaustive and requires O(n^{2}) 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 antidiagonal 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 antidiagonally ?
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 tictactoe 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;
}
}
return topLeftToBottomRight;
}
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 antidiagonal cells
// in a 3 X 3 tictactoe board: [0,2], [1,1], [2,0]
// What is the common things among all the antidiagonal
// 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 antidiagonal cell: col + row = length(tictactoe board)  1
if (row + col != grid.length1) {
return false;
}
boolean topRightToBottomLeft = true;
for (int columnIndex = 0; columnIndex < grid.length; columnIndex++) {
int rowIndex = grid.length  1  columnIndex; // for antidiagonal columnIndex + rowIndex = dimension of board  1
if (grid[columnIndex][rowIndex] != player) {
topRightToBottomLeft = false;
}
}
return topRightToBottomLeft;
}
}
/**
* 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 wellwritten 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 singleresponsibility 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 tictactoe 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 antidiagonal would have all 1's, which means the summation of the value in a row or column or diagonal or antidiagonal would be equal to the dimension of the given tictactoe 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 antidiagonal 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 antidiagonal
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 antidiagonal 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) { // antidiagonal 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);
*/
Check out our other System Design content here.

Click here to access our Premium Content on Algorithms .
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn