[LeetCode] Find Winner on a Tic Tac Toe Game

Problem: Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (" ").
• The first player A always places "X" characters, while the second player B always places "O" characters.
• "X" and "O" characters are always placed into empty squares, never on filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= moves[i][j] <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

Approach: The simplest way is to create a 2D array and then check for all the patterns but this will be expensive (m * n) both in terms of time and space. Let's try to do better. 

Let's define player A value is 1 and player B value is -1. We can take any value but this is just intuitive. Now let's see what are the winning combination of player A:

1. 'X' in all cells of a given row 
2. 'X' in all cells of a given column 
3. 'X' in all cells of diagonal
4. 'X in all cells of anti diagonal

That means if value of player A is 1. If the sum of any row or col or diagonal is 3 then player A is winner and similarly if the sum is -3 here then winner is player B.

We can take 2 1D arrays say rows and cols of size 3 (grid dimension) for maintaining the sums on every row and column. We can take two variables say diag1 and diag2 to maintain the sum on diagonal and anti diagonal.

With this our algorithm looks like:

• FOREACH move in moves
• row = move[0]
• col = move[1]
• rows[row] = rows[row] + playerVal
• cols[col] = cols[col] + playerVal
• IF row == col // On Diagonal
• diag1 = diag1 + playerVal
• IF row + col == gridDimension - 1 // On Anti Diagonal
• diag2 = diag2 + playerVal
• Here we check for our winner and return if any
• Change the playerVal, next turn
• Here we check if it is a draw or pending

That's all!

Implementation in C#:

    public string Tictactoe(int[][] moves) 

    {

        int gridDimension = 3;

        int[] rows = new int[gridDimension];

        int[] cols = new int[gridDimension];

        int valAtDiag1 = 0, valAtDiag2 = 0;

        int player = 1;

        foreach (int[] move in moves)

        {

            int moveRow = move[0];

            int moveCol = move[1];

            rows[moveRow] += player;

            cols[moveCol] += player;

            // Diagonal

            if (moveRow == moveCol)

            {

                valAtDiag1 += player;

            }

            // Anti Diagonal

            if (moveRow + moveCol == gridDimension - 1)

            {

                valAtDiag2 += player;

            }

            // Checking for winner

            if (Math.Abs(rows[moveRow]) == gridDimension 

                || Math.Abs(cols[moveCol]) == gridDimension 

                || Math.Abs(valAtDiag1) == gridDimension 

                || Math.Abs(valAtDiag2) == gridDimension)

            {

                return player == 1 ? "A" : "B";

            } 

            // Next player's turn

            player *= -1;

        }

        return moves.Length == gridDimension * gridDimension ? "Draw" : "Pending";

    }

Complexity: O(n)