Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:
- Players take turns placing characters into empty squares
' '. - The first player
Aalways places'X'characters, while the second playerBalways places'O'characters. 'X'and'O'characters are always placed into empty squares, never on filled ones.- The game ends when there are three 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 a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. 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 (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.
Example 1:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: "A" Explanation: A wins, they always play first.
Example 2:
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] Output: "B" Explanation: B wins.
Example 3:
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.
Constraints:
1 <= moves.length <= 9moves[i].length == 20 <= rowi, coli <= 2- There are no repeated elements on
moves. movesfollow the rules of tic tac toe.
Solution
Approach 1: Brute Force
class Solution {
// Initialize the board, n = 3 in this problem.
private int[][] board;
private int n = 3;
public String tictactoe(int[][] moves) {
board = new int[n][n];
int player = 1;
// For each move
for (int[] move : moves){
int row = move[0], col = move[1];
// Mark the current move with the current playrer's id.
board[row][col] = player;
// If any of the winning conditions is met, return the current player's id.
if (checkRow(row, player) ||
checkCol(col, player) ||
(row == col && checkDiagonal(player)) ||
(row + col == n - 1 && checkAntiDiagonal(player))){
return player == 1 ? "A" : "B";
}
// If no one wins so far, change to the other player alternatively.
// That is from 1 to -1, from -1 to 1.
player *= -1;
}
// If all moves are completed and there is still no result, we shall check if
// the grid is full or not. If so, the game ends with draw, otherwise pending.
return moves.length == n * n ? "Draw" : "Pending";
}
// Check if any of 4 winning conditions to see if the current player has won.
private boolean checkRow(int row, int player){
for (int col = 0; col < n; ++col){
if (board[row][col] != player) return false;
}
return true;
}
private boolean checkCol(int col, int player){
for (int row = 0; row < n; ++row){
if (board[row][col] != player) return false;
}
return true;
}
private boolean checkDiagonal(int player){
for (int row = 0; row < n; ++row){
if (board[row][row] != player) return false;
}
return true;
}
private boolean checkAntiDiagonal(int player){
for (int row = 0; row < n; ++row){
if (board[row][n - 1 - row] != player) return false;
}
return true;
}
} Complexity Analysis
Let n be the length of the board and m be the length of input moves.
- Time complexity:
For every move, we need to traverse the same row, column, diagonal, and anti-diagonal, which takes O(n) time.
- Space complexity: O(n^2)
We use an
nbynarray to record every move.
Approach 2: Record Each Move
class Solution {
public String tictactoe(int[][] moves) {
// n stands for the size of the board, n = 3 for the current game.
int n = 3;
// Use rows and cols to record the value on each row and each column.
// diag1 and diag2 to record value on diagonal or anti-diagonal.
int[] rows = new int[n], cols = new int[n];
int diag = 0, anti_diag = 0;
// Two players having value of 1 and -1, player_1 with value = 1 places first.
int player = 1;
for (int[] move : moves){
// Get the row number and column number for this move.
int row = move[0], col = move[1];
// Update the row value and column value.
rows[row] += player;
cols[col] += player;
// If this move is placed on diagonal or anti-diagonal,
// we shall update the relative value as well.
if (row == col){
diag += player;
}
if (row + col == n - 1){
anti_diag += player;
}
// Check if this move meets any of the winning conditions.
if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
Math.abs(diag) == n || Math.abs(anti_diag) == n){
return player == 1 ? "A" : "B";
}
// If no one wins so far, change to the other player alternatively.
// That is from 1 to -1, from -1 to 1.
player *= -1;
}
// If all moves are completed and there is still no result, we shall check if
// the grid is full or not. If so, the game ends with draw, otherwise pending.
return moves.length == n * n ? "Draw" : "Pending";
}
}Complexity Analysis
Let n be the length of the board and m be the length of input moves.
- Time complexity: O(m)
For every move, we update the value for a row, column, diagonal, and anti-diagonal. Each update takes constant time. We also check if any of these lines satisfies the winning condition which also takes constant time.
- Space complexity: O(n)
We use two arrays of size
nto record the value for each row and column, and two integers of constant space to record to value for diagonal and anti-diagonal.
CodeGuru 