Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:
' '.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.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 <= 2moves.moves follow the rules of tic tac toe.In #1275 Find Winner on a Tic Tac Toe Game, you are given a sequence of moves played by two players on a 3 x 3 grid. Player A and Player B alternate turns, and the goal is to determine whether A wins, B wins, the game ends in a draw, or it is still pending.
A clean way to solve this is by simulating the game while tracking how many marks each player places in every row, column, and diagonal. Instead of storing the entire board, you can maintain counters for rows, columns, and the two diagonals. Increment the counters for Player A and decrement them for Player B (or track them separately). If any counter reaches 3 or -3, that player has filled a row, column, or diagonal and wins the game.
Since there are at most 9 moves, the algorithm processes each move once. This results in O(n) time where n is the number of moves, and O(1) extra space because the board size is fixed.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row/Column Counter Simulation | O(n) | O(1) |
PaperBatMan
Use these hints if you're stuck. Try solving on your own first.
It's straightforward to check if A or B won or not, check for each row/column/diag if all the three are the same.
Then if no one wins, the game is a draw iff the board is full, i.e. moves.length = 9 otherwise is pending.
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.
Time Complexity: O(n), where n is the length of the moves. In the worst case, it checks 8 winning conditions for all 9 moves.
Space Complexity: O(1), since the board is of fixed size (3x3).
1#include <iostream>
2#include <vector>
3using namespace std;
4
5string tictactoe(vector<vector<int>>& moves) {
6 char board[3][3] = {{' ', ' ', ' '},{' ', ' ', ' '},{' ', ' ', ' '}};
7 char player = 'X';
8 for (auto& move : moves) {
9 board[move[0]][move[1]] = player;
10 player = (player == 'X') ? 'O' : 'X';
11 }
12 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;
}
The C++ solution uses a similar logic to the C solution but utilizes a C++ vector to store the moves. The main goal is to iterate through all moves, updating the board, and after each move, check for whether any player has won the game using row, column, and diagonal checks.
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.
Time Complexity: O(n), where n is the number of moves.
Space Complexity: O(1), as only fixed-size counters are involved.
#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;
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Simulation mirrors how the game is actually played by processing moves in order. This makes it easy to update row, column, and diagonal counters and immediately detect a winning condition without repeatedly scanning the board.
While this exact problem may not always appear, similar board simulation and state-tracking questions are common in technical interviews. It tests understanding of arrays, simulation logic, and efficient state updates.
Simple arrays are sufficient for this problem. Arrays can track row counts, column counts, and diagonal values while processing moves sequentially. Since the board is fixed at 3x3, the space usage remains constant.
The optimal approach tracks counts for rows, columns, and diagonals while simulating each move. By incrementing for one player and decrementing for the other, you can detect a winning line when any counter reaches 3 or -3. This avoids storing the entire board and keeps the solution efficient.
This approach leverages vectors to maintain scores for each row, column, and diagonal. The player alternation is expressed via the integer values -1 and 1. Once any score attains the absolute value of 3, a win is confirmed for the respective player.