Find Winner on a Tic Tac Toe Game solution and explanation
Google
9 more videos on this problem
Leetcode - Find Winner on a Tic Tac Toe Game (Python)Timothy H Chang · 5:17 · 9K views
Find Winner on a Tic Tac Toe Game | LeetCode 1275 | Theory + Python codeSai Anish Malla · 17:09 · 8K views
Find Winner on a Tic Tac Toe Game | Leetcode 1275 | Live coding session 🔥🔥🔥Coding Decoded · 7:28 · 8K views
Facebook Coding Interview Question | Leetcode 1275 | Find Winner on a Tic Tac Toe GameWorkWithGoogler · 5:54 · 1K views
1275 Find Winner on a Tic Tac Toe Game LeetcodeAnimated Anand · 7:07 · 980 views
Daily Leetcode #538: Sep 20, 2021 - 1275. Find Winner on a Tic Tac Toe GameProgramming Live with Larry · 10:44 · 893 views
LeetCode 1275 | Find Winner on a Tic Tac Toe Game | JavaSleepy Cracker · 10:22 · 583 views
1275. Find Winner on a Tic Tac Toe Game #leetcode #2darray #javaprogramming #dsa #dsalgo #codingCodeVia · 5:00 · 412 views
Leetcode | Easy | 1275. Find Winner on a Tic Tac Toe Game | Record Each Move | O(M) | JavascriptSoftware Interviews Prep · 22:19 · 335 views
LeetCode 1275 Find Winner on a Tic Tac Toe Game - PythonRan Fang · 28:46 · 327 views
The problem
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.
Approach overview
Problem Overview: You receive a list of moves for a 3x3 Tic Tac Toe game played by two players, A and B. Each move contains a row and column. After applying the moves in order, determine whether player A wins, player B wins, the game is a draw, or the game is still pending.
Approach 1: Simulation with a 3x3 Board (O(n) time, O(1) space)
Create a 3x3 board and simulate the game exactly as it would be played. Iterate through the moves array and place either 'A' or 'B' depending on whose turn it is. After filling the board, check all rows, columns, and the two diagonals for three identical marks. Since the board size is fixed (3x3), the win check is constant work. This approach is easy to reason about and mirrors the real game logic, making it a good starting point when working with matrix simulations.
Approach 2: Row and Column Count (O(n) time, O(1) space)
Instead of maintaining the full board, track counts for each row, column, and both diagonals. Player A adds +1 to the counters and player B adds -1. For every move, update rows[r], cols[c], and the diagonal counters if applicable. If any counter reaches 3 or -3, one player has filled that line and wins immediately. This technique avoids scanning the board and works well for problems involving incremental state updates using array counters and lightweight simulation.
Recommended for interviews: The row and column counting method is the preferred solution. It processes each move once and detects a win instantly without scanning the board. The board simulation approach demonstrates clear understanding of the game rules, but the counter technique shows stronger problem‑solving skills and awareness of constant-space optimizations.
Approach 1: Simulation with a 3x3 Board
In this approach, we use a 3x3 board to simulate the mechanics of a Tic Tac Toe game. For every move made, we place the respective player's symbol ('X' for player A and 'O' for player B) on the board. After each move, we check if this move results in a win for any player by verifying if there are three matching symbols in any row, column, or diagonal. If a win is found, that player is declared the winner and the game ends. If all moves are exhausted without a winner, the game is declared a draw. If there are remaining moves, the game is pending.
def tictactoe(moves):
board = [[' '] * 3 for _ in range(3)]
player = 'X'
for move in moves:
board[move[0]][move[1]] = player
player = 'O' if player == 'X' else 'X'
for i in range(3):
if board[i][0] != ' ' and board[i][0] == board[i][1] == board[i][2]:
return 'A' if board[i][0] == 'X' else 'B'
if board[0][i] != ' ' and board[0][i] == board[1][i] == board[2][i]:
return 'A' if board[0][i] == 'X' else 'B'
if board[0][0] != ' ' and board[0][0] == board[1][1] == board[2][2]:
return 'A' if board[0][0] == 'X' else 'B'
if board[0][2] != ' ' and board[0][2] == board[1][1] == board[2][0]:
return 'A' if board[0][2] == 'X' else 'B'
return "Draw" if len(moves) == 9 else "Pending"
# Example usage
moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
print(tictactoe(moves))class Solution {
public String tictactoe(int[][] moves) {
char[][] board = new char[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[i][j] = ' ';
}
}
char currentPlayer = 'X';
for (int[] move : moves) {
board[move[0]][move[1]] = currentPlayer;
currentPlayer = currentPlayer == 'X' ? 'O' : 'X';
}
for (int i = 0; i < 3; i++) {
if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2]) return board[i][0] == 'X' ? "A" : "B";
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i]) return board[0][i] == 'X' ? "A" : "B";
}
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2]) return board[0][0] == 'X' ? "A" : "B";
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0]) return board[0][2] == 'X' ? "A" : "B";
return moves.length == 9 ? "Draw" : "Pending";
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] moves = {{0,0},{2,0},{1,1},{2,1},{2,2}};
System.out.println(sol.tictactoe(moves));
}
}#include <iostream>
#include <vector>
using namespace std;
string tictactoe(vector<vector<int>>& moves) {
char board[3][3] = {{' ', ' ', ' '},{' ', ' ', ' '},{' ', ' ', ' '}};
char player = 'X';
for (auto& move : moves) {
board[move[0]][move[1]] = player;
player = (player == 'X') ? 'O' : 'X';
}
for (int i = 0; i < 3; ++i) {
if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
return (board[i][0] == 'X') ? "A" : "B";
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
return (board[0][i] == 'X') ? "A" : "B";
}
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
return (board[0][0] == 'X') ? "A" : "B";
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
return (board[0][2] == 'X') ? "A" : "B";
return moves.size() == 9 ? "Draw" : "Pending";
}
int main() {
vector<vector<int>> moves = {{0,0},{2,0},{1,1},{2,1},{2,2}};
cout << tictactoe(moves) << endl;
return 0;
}function tictactoe(moves) {
const board = Array.from({length: 3}, () => Array(3).fill(' '));
let player = 'X';
for (const [x, y] of moves) {
board[x][y] = player;
player = player === 'X' ? 'O' : 'X';
}
for (let i = 0; i < 3; i++) {
if (board[i][0] !== ' ' && board[i][0] === board[i][1] && board[i][1] === board[i][2])
return board[i][0] === 'X' ? "A" : "B";
if (board[0][i] !== ' ' && board[0][i] === board[1][i] && board[1][i] === board[2][i])
return board[0][i] === 'X' ? "A" : "B";
}
if (board[0][0] !== ' ' && board[0][0] === board[1][1] && board[1][1] === board[2][2])
return board[0][0] === 'X' ? "A" : "B";
if (board[0][2] !== ' ' && board[0][2] === board[1][1] && board[1][1] === board[2][0])
return board[0][2] === 'X' ? "A" : "B";
return moves.length === 9 ? "Draw" : "Pending";
}
// Example usage
console.log(tictactoe([[0,0],[2,0],[1,1],[2,1],[2,2]]));#include <stdio.h>
#include <string.h>
const char* tictactoe(int moves[][2], int movesSize) {
char board[3][3];
memset(board, ' ', sizeof(board));
int currentPlayer = 0;
char symbols[2] = {'X', 'O'};
for (int i = 0; i < movesSize; ++i) {
int row = moves[i][0];
int col = moves[i][1];
board[row][col] = symbols[currentPlayer];
currentPlayer = 1 - currentPlayer;
}
for (int i = 0; i < 3; ++i) {
if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
return board[i][0] == 'X' ? "A" : "B";
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
return board[0][i] == 'X' ? "A" : "B";
}
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
return board[0][0] == 'X' ? "A" : "B";
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
return board[0][2] == 'X' ? "A" : "B";
return movesSize == 9 ? "Draw" : "Pending";
}
int main() {
int moves[][2] = {{0,0},{2,0},{1,1},{2,1},{2,2}};
const char* result = tictactoe(moves, sizeof(moves) / sizeof(moves[0]));
printf("%s\n", result);
return 0;
}using System;
public class Solution {
public string Tictactoe(int[][] moves) {
char[,] board = new char[3,3];
char player = 'X';
foreach (var move in moves) {
board[move[0],move[1]] = player;
player = player == 'X' ? 'O' : 'X';
}
for (int i = 0; i < 3; i++) {
if (board[i,0] != '\0' && board[i,0] == board[i,1] && board[i,1] == board[i,2])
return board[i,0] == 'X' ? "A" : "B";
if (board[0,i] != '\0' && board[0,i] == board[1,i] && board[1,i] == board[2,i])
return board[0,i] == 'X' ? "A" : "B";
}
if (board[0,0] != '\0' && board[0,0] == board[1,1] && board[1,1] == board[2,2])
return board[0,0] == 'X' ? "A" : "B";
if (board[0,2] != '\0' && board[0,2] == board[1,1] && board[1,1] == board[2,0])
return board[0,2] == 'X' ? "A" : "B";
return moves.Length == 9 ? "Draw" : "Pending";
}
public static void Main(string[] args) {
int[][] moves = new int[][] { new int[] {0,0}, new int[] {2,0}, new int[] {1,1}, new int[] {2,1}, new int[] {2,2} };
Solution sol = new Solution();
Console.WriteLine(sol.Tictactoe(moves));
}
}This Python implementation keeps track of a 3x3 board, updates it with moves, and checks possible winning conditions. The player alternates between 'X' and 'O' after each move. If a win is detected, the respective player is declared the winner; otherwise, the game is checked for a draw or set as pending.
Time Complexity: O(n), where n is the length of the moves list. Each move is evaluated with constant time checks.
Space Complexity: O(1), as the board size is static.
Approach 2: Row and Column Count
Instead of simulating the grid itself, this approach tracks the status of each row, column, and the two diagonals using counters. Each player will have their counters, incrementing or decrementing upon making a move. The first instance a counter reaches 3 or -3 indicates a player has won the game. This method significantly reduces the need to check the grid extensively for each move while still adhering to the rules of Tic Tac Toe.
def tictactoe(moves):
row = [0] * 3
col = [0] * 3
diag = 0
anti_diag = 0
player = 1
for r, c in moves:
row[r] += player
col[c] += player
diag += player if r == c else 0
anti_diag += player if r + c == 2 else 0
if abs(row[r]) == 3 or abs(col[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
return "A" if player == 1 else "B"
player *= -1
return "Draw" if len(moves) == 9 else "Pending"
# Example usage
moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
print(tictactoe(moves))public class Solution {
public String tictactoe(int[][] moves) {
int[] row = new int[3], col = new int[3];
int diag = 0, antiDiag = 0;
int player = 1;
for (int[] move : moves) {
int r = move[0], c = move[1];
row[r] += player;
col[c] += player;
if (r == c) diag += player;
if (r + c == 2) antiDiag += player;
if (Math.abs(row[r]) == 3 || Math.abs(col[c]) == 3 || Math.abs(diag) == 3 || Math.abs(antiDiag) == 3)
return player == 1 ? "A" : "B";
player = -player;
}
return moves.length == 9 ? "Draw" : "Pending";
}
public static void main(String[] args) {
int[][] moves = {{0,0},{2,0},{1,1},{2,1},{2,2}};
Solution sol = new Solution();
System.out.println(sol.tictactoe(moves));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
string tictactoe(vector<vector<int>>& moves) {
vector<int> row(3, 0), col(3, 0);
int diag = 0, anti_diag = 0;
int player = 1;
for (auto& move : moves) {
int r = move[0], c = move[1];
row[r] += player;
col[c] += player;
if (r == c) diag += player;
if (r + c == 2) anti_diag += player;
if (abs(row[r]) == 3 || abs(col[c]) == 3 || abs(diag) == 3 || abs(anti_diag) == 3)
return player == 1 ? "A" : "B";
player = -player;
}
return moves.size() == 9 ? "Draw" : "Pending";
}
int main() {
vector<vector<int>> moves = {{0,0},{2,0},{1,1},{2,1},{2,2}};
cout << tictactoe(moves) << endl;
return 0;
}function tictactoe(moves) {
const row = [0, 0, 0];
const col = [0, 0, 0];
let diag = 0, antiDiag = 0, player = 1;
for (const [r, c] of moves) {
row[r] += player;
col[c] += player;
if (r === c) diag += player;
if (r + c === 2) antiDiag += player;
if (Math.abs(row[r]) === 3 || Math.abs(col[c]) === 3 || Math.abs(diag) === 3 || Math.abs(antiDiag) === 3)
return player === 1 ? "A" : "B";
player *= -1;
}
return moves.length === 9 ? "Draw" : "Pending";
}
// Example usage
console.log(tictactoe([[0,0],[2,0],[1,1],[2,1],[2,2]]));#include <stdio.h>
#include <stdlib.h>
const char* tictactoe(int moves[][2], int movesSize) {
int row[3] = {0}, col[3] = {0}, diag = 0, anti_diag = 0;
int player = 1;
for (int i = 0; i < movesSize; ++i) {
int r = moves[i][0], c = moves[i][1];
row[r] += player;
col[c] += player;
if (r == c) diag += player;
if (r + c == 2) anti_diag += player;
if (abs(row[r]) == 3 || abs(col[c]) == 3 || abs(diag) == 3 || abs(anti_diag) == 3)
return player == 1 ? "A" : "B";
player = -player;
}
return movesSize == 9 ? "Draw" : "Pending";
}
int main() {
int moves[][2] = {{0,0},{2,0},{1,1},{2,1},{2,2}};
printf("%s\n", tictactoe(moves, 5));
return 0;
}using System;
public class Solution {
public string Tictactoe(int[][] moves) {
int[] row = new int[3];
int[] col = new int[3];
int diag = 0, antiDiag = 0;
int player = 1;
foreach (var move in moves) {
int r = move[0], c = move[1];
row[r] += player;
col[c] += player;
if (r == c) diag += player;
if (r + c == 2) antiDiag += player;
if (Math.Abs(row[r]) == 3 || Math.Abs(col[c]) == 3 || Math.Abs(diag) == 3 || Math.Abs(antiDiag) == 3)
return player == 1 ? "A" : "B";
player *= -1;
}
return moves.Length == 9 ? "Draw" : "Pending";
}
public static void Main(string[] args) {
int[][] moves = new int[][] { new int[] {0,0}, new int[] {2,0}, new int[] {1,1}, new int[] {2,1}, new int[] {2,2} };
Solution sol = new Solution();
Console.WriteLine(sol.Tictactoe(moves));
}
}Using simple arithmetic operations on list elements and auxiliary variables, this Python solution tracks changes in game progression. Appropriate checks reveal when a winning condition is achieved. Alternating move processing relies on changing player values from 1 to -1.
Time Complexity: O(n), proportional directly to move count.
Space Complexity: O(1), since only scores and counters are employed.
Approach 3: Determine if the last player to move can win
Since all moves are valid, that is, there is no situation where a person continues to play after someone has won. Therefore, we only need to determine whether the last player to move can win.
We use an array cnt of length 8 to record the number of moves in rows, columns, and diagonals. Where cnt[0, 1, 2] represent the number of moves in the 0, 1, 2 rows respectively, and cnt[3, 4, 5] represent the number of moves in the 0, 1, 2 columns respectively. Additionally, cnt[6] and cnt[7] represent the number of moves on the two diagonals respectively. During the game, if a player makes 3 moves in a row, column, or diagonal, that player wins.
If the last player to move does not win, then we determine whether the board is full. If it is full, it is a draw; otherwise, the game is not over yet.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of moves.
function tictactoe(moves: number[][]): string {
const n = moves.length;
const cnt = new Array(8).fill(0);
for (let k = n - 1; k >= 0; k -= 2) {
const [i, j] = moves[k];
cnt[i]++;
cnt[j + 3]++;
if (i == j) {
cnt[6]++;
}
if (i + j == 2) {
cnt[7]++;
}
if (cnt[i] == 3 || cnt[j + 3] == 3 || cnt[6] == 3 || cnt[7] == 3) {
return k % 2 == 0 ? 'A' : 'B';
}
}
return n == 9 ? 'Draw' : 'Pending';
}func tictactoe(moves [][]int) string {
n := len(moves)
cnt := [8]int{}
for k := n - 1; k >= 0; k -= 2 {
i, j := moves[k][0], moves[k][1]
cnt[i]++
cnt[j+3]++
if i == j {
cnt[6]++
}
if i+j == 2 {
cnt[7]++
}
if cnt[i] == 3 || cnt[j+3] == 3 || cnt[6] == 3 || cnt[7] == 3 {
if k%2 == 0 {
return "A"
}
return "B"
}
}
if n == 9 {
return "Draw"
}
return "Pending"
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulation with a 3x3 Board | Time Complexity: O(n), where n is the length of the moves list. Each move is evaluated with constant time checks. |
| Row and Column Count | Time Complexity: O(n), proportional directly to move count. |
| Determine if the last player to move can win | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with 3x3 Board | O(n) | O(1) | Best when you want straightforward logic that mirrors the actual game board |
| Row and Column Count | O(n) | O(1) | Optimal approach when you want constant-time win detection without scanning the board |
Frequently asked questions
Is Find Winner on a Tic Tac Toe Game easy or hard?
Find Winner on a Tic Tac Toe Game is classified as an Easy problem. The logic mainly involves simulation and simple counting techniques using arrays, making it approachable for beginners practicing matrix and game-state problems.
Find Winner on a Tic Tac Toe Game Python/Java solution
Python and Java implementations usually follow the row/column counting strategy. Use arrays of size three for rows and columns, update them for each move, and check whether any value reaches 3 or -3 to determine the winner.
How to solve Find Winner on a Tic Tac Toe Game in O(n)?
Iterate through the moves once while updating row, column, and diagonal counters. Add +1 for player A and -1 for player B. If the absolute value of any counter becomes 3, a player has filled that entire row, column, or diagonal and wins immediately.
What is the best approach for Find Winner on a Tic Tac Toe Game?
The row and column counting approach is the most efficient. Maintain counters for each row, column, and diagonal. Player A increments by +1 and player B decrements by -1. When any counter reaches 3 or -3, that player wins. This detects the winner in O(n) time with O(1) extra space.
Is Find Winner on a Tic Tac Toe Game asked at Google/Amazon/Meta?
Tic Tac Toe simulation and board-state problems frequently appear in coding interviews at companies like Google, Amazon, and Meta. They test array manipulation, matrix reasoning, and the ability to track incremental state efficiently.
What data structure is used in Find Winner on a Tic Tac Toe Game?
The solution typically uses arrays to store row and column counts and two variables for diagonals. A simple 3x3 matrix can also be used when simulating the board directly.
What is the time complexity of Find Winner on a Tic Tac Toe Game?
Both common solutions run in O(n) time where n is the number of moves. Each move is processed once. The board size is fixed at 3x3, so checking rows, columns, and diagonals is constant work. Space complexity remains O(1).