hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Tic-Tac-Toe Winner
Problem: Tic-Tac-Toe Winner
Problem Link: https://www.codingninjas.com/codestudio/problems/tic-tac-toe-winner_1214545
Approach:
Initiated a 3x3 matrix, say, board.
Inserted the entry of moves into the board.
Checked if the winner was found with the current board state.
If the winner was found, returned player1 and player2.
If there are fewer than 9 moves without finding the winner then, returned uncertain.
Otherwise, returned draw.
Time and Space Complexity:
Time Complexity: O(N), N = 9 X N
Space Complexity: O(1)
Code [C++]
#include <bits/stdc++.h>
int is_winner_found(vector<vector<int>> & board){
// Column
if(board[0][0] == board[1][0] && board[1][0] == board[2][0]) return board[0][0];
if(board[0][1] == board[1][1] && board[1][1] == board[2][1]) return board[0][1];
if(board[0][2] == board[1][2] && board[1][2] == board[2][2]) return board[0][2];
// Row
if(board[0][0] == board[0][1] && board[0][1] == board[0][2]) return board[0][0];
if(board[1][0] == board[1][1] && board[1][1] == board[1][2]) return board[1][0];
if(board[2][0] == board[2][1] && board[2][1] == board[2][2]) return board[2][0];
// Diagonal
if(board[0][0] == board[1][1] && board[1][1] == board[2][2]) return board[0][0];
if(board[0][2] == board[1][1] && board[1][1] == board[2][0]) return board[0][2];
return -1;
}
string ticTacToeWinner(vector<vector<int>> moves, int n) {
vector<vector<int>> board (3, vector<int>(3, 0));
int move = 2;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
board[i][j] = ++move;
}
}
move = 0;
for(int i=0; i<n; i++){
board[moves[i][0]][moves[i][1]] = move;
int verdict = is_winner_found(board);
if(verdict != -1){
if(verdict == 0) return "player1";
else return "player2";
}
move ^= 1;
}
if(n != 9) return "uncertain";
return "draw";
}