LeetCode 1275: Find Winner on a Tic Tac Toe Game
Problem Description
Explanation:
To solve this problem, we can simulate the tic-tac-toe game based on the provided moves and check for a winner or a draw condition after each move. We can represent the game board as a 3x3 grid and keep track of which player made each move. We need to check for winning conditions after each move by checking rows, columns, and diagonals.
- Initialize a 3x3 grid to represent the tic-tac-toe board.
- Iterate through the moves array and update the board based on the player's move.
- After each move, check if there is a winning condition by checking rows, columns, and diagonals for three consecutive marks by the same player.
- If a winning condition is met, return the winner (A or B).
- If all moves are made and no winner is determined, return "Draw".
- If there are still moves to be made, return "Pending".
Time Complexity: O(1) as there are a limited number of moves in a 3x3 tic-tac-toe game. Space Complexity: O(1) as we are using a fixed-size grid to represent the game board.
Solutions
class Solution {
public String tictactoe(int[][] moves) {
char[][] grid = new char[3][3];
char player = 'X';
for (int[] move : moves) {
grid[move[0]][move[1]] = player;
if (checkWin(grid, move[0], move[1], player)) {
return player == 'X' ? "A" : "B";
}
player = player == 'X' ? 'O' : 'X';
}
return moves.length == 9 ? "Draw" : "Pending";
}
private boolean checkWin(char[][] grid, int row, int col, char player) {
// Check row
if (grid[row][0] == player && grid[row][1] == player && grid[row][2] == player) {
return true;
}
// Check column
if (grid[0][col] == player && grid[1][col] == player && grid[2][col] == player) {
return true;
}
// Check diagonals
if ((row == col || row + col == 2)
&& ((grid[0][0] == player && grid[1][1] == player && grid[2][2] == player)
|| (grid[0][2] == player && grid[1][1] == player && grid[2][0] == player))) {
return true;
}
return false;
}
}Loading editor...