Find Winner on a Tic Tac Toe Game

Easy

#1189Time: O(1), because the number of moves is at most 9 and the grid size is fixed at 3x3. The loops for populating and checking the grid run a constant number of times.Space: O(1), as we use a fixed-size 3x3 grid, which does not depend on the number of moves.3 companies

Data structures

Array Hash Table Matrix

Companies

Qualcomm Zoho Tesla

Prompt

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] = [row_i, col_i] indicates that the i^th move will be played on grid[row_i][col_i]. 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 <= 9
moves[i].length == 2
0 <= row_i, col_i <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the game by creating a 3x3 grid and placing the moves of players A and B according to the input. After all given moves are placed on the grid, it performs a check of all 8 possible winning lines (3 rows, 3 columns, and 2 diagonals) to determine if a player has won. If no winner is found, it checks if the board is full to declare a draw or if the game is still pending.

Algorithm

Initialize a 3x3 char array grid to represent the game board.
Iterate through the moves array. For each move at index i:
- If i is even, it's Player A's turn. Place 'X' at grid[moves[i][0]][moves[i][1]].
- If i is odd, it's Player B's turn. Place 'O' at grid[moves[i][0]][moves[i][1]].
After populating the grid, create a helper function isWinner(grid, player) to check for a win.
Inside isWinner, check all 8 winning lines (3 rows, 3 columns, 2 diagonals) for the specified player character.
Call isWinner(grid, 'X'). If it returns true, the winner is "A".
Call isWinner(grid, 'O'). If it returns true, the winner is "B".
If no winner is found, check if the number of moves is 9. If so, the game is a "Draw".
Otherwise, the game is still in progress, so the result is "Pending".

Walkthrough

First, we initialize a 3x3 character array grid to represent the Tic-Tac-Toe board. We then iterate through the moves array. For each move, we determine the current player based on the index of the move. Player A makes moves at even indices (0, 2, 4, ...) and places 'X', while Player B makes moves at odd indices (1, 3, 5, ...) and places 'O'. We update the grid with the corresponding character at the specified [row, col].

After populating the grid with all the moves, we check for a winner. We can write a helper function that takes the grid and a player's character ('X' or 'O') and returns true if that player has won. This function checks all 3 rows, 3 columns, and 2 diagonals. If it finds any line completely filled with the player's character, it confirms a win.

We first check if player A has won. If so, we return "A". Then we check for player B. If B has won, we return "B". If neither player has won, we check the total number of moves. If moves.length is 9, the board is full, and the game is a "Draw". Otherwise, there are still empty squares and no winner, so the game is "Pending".

1class Solution {2    public String tictactoe(int[][] moves) {3        char[][] grid = new char[3][3];4        for (int i = 0; i < moves.length; i++) {5            int r = moves[i][0];6            int c = moves[i][1];7            if (i % 2 == 0) {8                grid[r][c] = 'X'; // Player A9            } else {10                grid[r][c] = 'O'; // Player B11            }12        }13 14        if (isWinner(grid, 'X')) {15            return "A";16        }17        if (isWinner(grid, 'O')) {18            return "B";19        }20 21        if (moves.length == 9) {22            return "Draw";23        } else {24            return "Pending";25        }26    }27 28    private boolean isWinner(char[][] grid, char player) {29        // Check rows30        for (int i = 0; i < 3; i++) {31            if (grid[i][0] == player && grid[i][1] == player && grid[i][2] == player) {32                return true;33            }34        }35        // Check columns36        for (int i = 0; i < 3; i++) {37            if (grid[0][i] == player && grid[1][i] == player && grid[2][i] == player) {38                return true;39            }40        }41        // Check diagonals42        if (grid[0][0] == player && grid[1][1] == player && grid[2][2] == player) {43            return true;44        }45        if (grid[0][2] == player && grid[1][1] == player && grid[2][0] == player) {46            return true;47        }48        return false;49    }50}

Complexity

Time

O(1), because the number of moves is at most 9 and the grid size is fixed at 3x3. The loops for populating and checking the grid run a constant number of times.

Space

O(1), as we use a fixed-size 3x3 grid, which does not depend on the number of moves.

Trade-offs

Pros

The logic is very straightforward and easy to follow, as it mimics the actual gameplay.
Simple to implement and debug.

Cons

It processes all moves before checking for a winner, even if a win occurred earlier in the game.
Slightly more memory usage due to the 3x3 grid compared to just using counters.

This optimized approach avoids creating a full grid. Instead, it keeps track of the progress on each of the 8 winning lines using counters. We use an array for rows, an array for columns, and two variables for the diagonals. Player A's moves increment the counters, while Player B's moves decrement them. A win is detected as soon as any counter reaches a sum of 3 (for A) or -3 (for B), allowing the algorithm to terminate early.

Algorithm

Initialize integer arrays rows and cols of size 3, and two integer variables diag1 and diag2, all to 0.
Define a player variable, starting at 1 for Player A. We will use 1 for A and -1 for B.
Iterate through the moves array. For each move [r, c]:
- Add the player value to rows[r] and cols[c].
- If the move is on the main diagonal (r == c), add player to diag1.
- If the move is on the anti-diagonal (r + c == 2), add player to diag2.
- After updating, check if the absolute value of any of the updated counts (rows[r], cols[c], diag1, diag2) is equal to 3.
- If it is, a winner has been found. Return "A" if player is 1, or "B" if player is -1.
- Flip the sign of the player variable (player *= -1) to switch to the other player for the next turn.
If the loop completes without a winner, check if moves.length is 9. If so, return "Draw".
Otherwise, return "Pending".

Walkthrough

Instead of building a 2D grid, we can use a more direct method to track winning conditions. We maintain counts for each of the 3 rows, 3 columns, and 2 diagonals. We can use a value of +1 for Player A and -1 for Player B.

We initialize two arrays, rows and cols, of size 3, and two integer variables, diag1 and diag2, to store the scores for each line. We then iterate through the moves. For each move [r, c], we identify the current player. Let's say Player A is 1 and Player B is -1. We add the player's value to rows[r], cols[c]. If the move lies on a diagonal, we also update the corresponding diagonal's score (diag1 if r == c, diag2 if r + c == 2).

After each move, we check if any of the updated scores have reached 3 or -3. If rows[r], cols[c], diag1, or diag2 equals 3, Player A has won. If any of them equal -3, Player B has won. If a winner is found, we can immediately return the result ("A" or "B") without processing the rest of the moves.

If the loop finishes without finding a winner, it means no one has won yet. We then check if all 9 moves have been played (moves.length == 9). If so, it's a "Draw". Otherwise, the game is still "Pending".

1class Solution {2    public String tictactoe(int[][] moves) {3        int[] rows = new int[3];4        int[] cols = new int[3];5        int diag1 = 0;6        int diag2 = 0;7        int player = 1; // 1 for A, -1 for B8 9        for (int i = 0; i < moves.length; i++) {10            int r = moves[i][0];11            int c = moves[i][1];12 13            rows[r] += player;14            cols[c] += player;15            if (r == c) {16                diag1 += player;17            }18            if (r + c == 2) {19                diag2 += player;20            }21 22            // Check for winner23            if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3 ||24                Math.abs(diag1) == 3 || Math.abs(diag2) == 3) {25                return player == 1 ? "A" : "B";26            }27 28            // Switch player29            player *= -1;30        }31 32        // No winner yet, check for Draw or Pending33        return moves.length == 9 ? "Draw" : "Pending";34    }35}

Complexity

Time

O(N), where N is the number of moves. Since N is at most 9, this is effectively O(1). It is faster in practice than the simulation approach because it can find a winner before iterating through all moves.

Space

O(1), as it uses a fixed number of variables and small arrays (3+3+2 = 8 integers) regardless of the input size.

Trade-offs

Pros

Highly efficient as it checks for a winner after each move and can terminate early.
Minimal space usage, only requiring a few integer arrays and variables.
Processes each move in constant time.

Cons

The logic of using +1/-1 and checking sums might be slightly less intuitive than visually checking a grid.

Solutions

Solution

1class Solution {2public3  String tictactoe(int[][] moves) {4    int n = moves.length;5    int[] cnt = new int[8];6    for (int k = n - 1; k >= 0; k -= 2) {7      int i = moves[k][0], j = moves[k][1];8      cnt[i]++;9      cnt[j + 3]++;10      if (i == j) {11        cnt[6]++;12      }13      if (i + j == 2) {14        cnt[7]++;15      }16      if (cnt[i] == 3 || cnt[j + 3] == 3 || cnt[6] == 3 || cnt[7] == 3) {17        return k % 2 == 0 ? "A" : "B";18      }19    }20    return n == 9 ? "Draw" : "Pending";21  }22}

1class Solution {2public:3  string tictactoe(vector<vector<int>> &moves) {4    int n = moves.size();5    int cnt[8]{};6    for (int k = n - 1; k >= 0; k -= 2) {7      int i = moves[k][0], j = moves[k][1];8      cnt[i]++;9      cnt[j + 3]++;10      if (i == j) {11        cnt[6]++;12      }13      if (i + j == 2) {14        cnt[7]++;15      }16      if (cnt[i] == 3 || cnt[j + 3] == 3 || cnt[6] == 3 || cnt[7] == 3) {17        return k % 2 == 0 ? "A" : "B";18      }19    }20    return n == 9 ? "Draw" : "Pending";21  }22};

1class Solution:2    def tictactoe(self, moves: List[List[int]]) -> str: n = len(moves) cnt = [0] * 8 for k in range(n - 1, - 1, - 2): i, j = moves[k] cnt[i] += 1 cnt[j + 3] += 1 if i == j: cnt[6] += 1 if i + j == 2: cnt[7] += 1 if any(v == 3 for v in cnt): return "B" if k & 1 else "A" return "Draw" if n == 9 else "Pending"

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem