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;
            }
        }
        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 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;
            }
        }
        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 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);
 */





The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave