Approach
There are 8 ways to win Tic-tac-toe for a player, i.e., 3 columns, 3 rows, and 2 diagonals. Both A and B players make a move alternatively. So, all the odd moves are for player A and even moves for player B.
Now, to track the movement of the players and if the winning positions are filled up, an array for each player is maintained.
Each index in the player’s array holds a specific meaning:
0,1,2 index for rows
3,4,5 index for columns
6 index for diagonal (top left to bottom right)
7 index for diagonal (top right to bottom left)
0 1 2 columns
0 [ ] [ ] [ ]
1 [ ] [ ] [ ]
2 [ ] [ ] [ ]
Rows
So, if move made at row 0, 1 or 2 ----> player[row] is updated
if move made at column 0,1 or 2 ----> player[column + 3] is updated
If move made at diagonal (top left to bottom right) ({0,0}, {1,1}, {2,2}) -----> player[6] is updated (i.e. r == c condition in checked)
If move made at diagonal (top right to bottom left) ({2,0}, {1,1}, {0,2}) -----> player[7] is updated (i.e. r == 2 - c condition in checked)
Implementation
Let’s have a look at its implementation in Java :
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter number of moves");
int n = s.nextInt();
int[][] moves = new int[n][2];
System.out.println("Enter moves");
for (int i = 0; i < n; i++) {
moves[i][0] = s.nextInt();
moves[i][1] = s.nextInt();
}
String ans = tictactoe(moves);
System.out.println("Output is: "+ ans);
}
public static String tictactoe(int[][] moves) {
// Creating 8 sized array for 3 rows, 3 cols, 2 diagonals
int[] A = new int[8];
int[] B = new int[8];
// Traversing the moves array
for(int i = 0; i < moves.length; i++) {
int r = moves[i][0];
int c = moves[i][1];
int[] player = (i % 2 == 0) ? A : B;
player[r]++;
player[c + 3]++;
// For diagonals
if(r == c) player[6]++;
if(r == 2 - c) player[7]++;
}
// Finding out the winner
for(int i = 0; i < 8; i++) {
if(A[i] == 3) return "A";
if(B[i] == 3) return "B";
}
if (moves.length == 9) return "Draw";
else return "Pending";
}
}

You can also try this code with Online Java Compiler
Run Code
Output:
Enter number of moves
6
Enter moves
0 0
1 1
0 1
0 2
1 0
2 0
Output is: B
Complexity Analysis
Time Complexity: The time complexity is O(N) where ‘N’ is the number of moves as the ‘moves[]’ array is only traversed once (i.e. number of rows).
Space Complexity: The space complexity is O(1) or O(8 + 8) as 8-sized two arrays A and B are created for storing moves for 3 rows, 3 columns, and 2 diagonals for A and B players.
Read More - Time Complexity of Sorting Algorithms
Frequently Asked Questions
What is tic-tac-toe?
Tic-Tac-Toe is a simple and fun game for 2 players, X and O. It is played on a 3x3 grid. Each player's goal is to make 3 in a row.
What are arrays?
An array is a collection of multiple items of the same type stored at contiguous memory locations.
What is the time complexity for the Winner of the Tic-tac-toe Problem?
The time complexity for Tic-tac-toe Problem is O(N) where ‘N’ is the number of moves as the ‘moves[]’ array is only traversed once (i.e. number of rows).
Conclusion
In this blog, we learned various approaches to the Winner of the Tic-tac-toe Problem.
- The winner of the Tic-tac-toe Problem is a standard easy problem that could be solved via arrays.
- Here we map the moves of the 8 winning positions to each index of the player’s array
-
The optimized time complexity of this problem is O(N) where ‘N’ is the number of moves.
Recommended Problems:
Recommended Readings:
Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.
Happy Coding!