1275. Find Winner on a Tic Tac Toe Game LeetCode Solution
In this guide, you will get 1275. Find Winner on a Tic Tac Toe Game LeetCode Solution with the best time and space complexity. The solution to Find Winner on a Tic Tac Toe Game problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Winner on a Tic Tac Toe Game
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 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 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.
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 <= 9
moves[i].length == 2
0 <= rowi, coli <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.
Complexity Analysis
Time Complexity:
Space Complexity:
1275. Find Winner on a Tic Tac Toe Game LeetCode Solution in C++
class Solution {
public:
string tictactoe(vector<vector<int>>& moves) {
vector<vector<int>> row(2, vector<int>(3));
vector<vector<int>> col(2, vector<int>(3));
vector<int> diag1(2);
vector<int> diag2(2);
for (int i = 0; i < moves.size(); ++i) {
const int r = moves[i][0];
const int c = moves[i][1];
const int j = i & 1;
if (++row[j][r] == 3 || ++col[j][c] == 3 || r == c && ++diag1[j] == 3 ||
r + c == 2 && ++diag2[j] == 3)
return j == 0 ? "A" : "B";
}
return moves.size() == 9 ? "Draw" : "Pending";
}
}; /* code provided by PROGIEZ */
1275. Find Winner on a Tic Tac Toe Game LeetCode Solution in Java
class Solution {
public String tictactoe(int[][] moves) {
int[][] row = new int[2][3];
int[][] col = new int[2][3];
int[] diag1 = new int[2];
int[] diag2 = new int[2];
for (int i = 0; i < moves.length; ++i) {
final int r = moves[i][0];
final int c = moves[i][1];
final int j = i & 1;
if (++row[j][r] == 3 || ++col[j][c] == 3 || r == c && ++diag1[j] == 3 ||
r + c == 2 && ++diag2[j] == 3)
return j == 0 ? "A" : "B";
}
return moves.length == 9 ? "Draw" : "Pending";
}
} // code provided by PROGIEZ
1275. Find Winner on a Tic Tac Toe Game LeetCode Solution in Python
class Solution:
def tictactoe(self, moves: list[list[int]]) -> str:
row = [[0] * 3 for _ in range(2)]
col = [[0] * 3 for _ in range(2)]
diag1 = [0] * 2
diag2 = [0] * 2
i = 0
for r, c in moves:
row[i][r] += 1
col[i][c] += 1
diag1[i] += r == c
diag2[i] += r + c == 2
if 3 in (row[i][r], col[i][c], diag1[i], diag2[i]):
return 'A' if i == 0 else 'B'
i ^= 1
return 'Draw' if len(moves) == 9 else 'Pending' # code by PROGIEZ
