# Find Winner on a Tic Tac Toe Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game)
Canonical: https://scaleengineer.com/dsa/problems/find-winner-on-a-tic-tac-toe-game
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Zoho](https://scaleengineer.com/companies/zoho), [Tesla](https://scaleengineer.com/companies/tesla)
---
## 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 `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] = [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:**

![](https://assets.glich.co/dsa/find-winner-on-a-tic-tac-toe-game/image0.jpg) 

**Input:** moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
**Output:** "A"
**Explanation:** A wins, they always play first.

**Example 2:**

![](https://assets.glich.co/dsa/find-winner-on-a-tic-tac-toe-game/image1.jpg) 

**Input:** moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
**Output:** "B"
**Explanation:** B wins.

**Example 3:**

![](https://assets.glich.co/dsa/find-winner-on-a-tic-tac-toe-game/image2.jpg) 

**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 <= rowi, coli <= 2`
* There are no repeated elements on `moves`.
* `moves` follow the rules of tic tac toe.

# Approaches
## Simulation and Brute-Force Check
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.
**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.
**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.
### Explanation
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".

```java
class Solution {
    public String tictactoe(int[][] moves) {
        char[][] grid = new char[3][3];
        for (int i = 0; i < moves.length; i++) {
            int r = moves[i][0];
            int c = moves[i][1];
            if (i % 2 == 0) {
                grid[r][c] = 'X'; // Player A
            } else {
                grid[r][c] = 'O'; // Player B
            }
        }

        if (isWinner(grid, 'X')) {
            return "A";
        }
        if (isWinner(grid, 'O')) {
            return "B";
        }

        if (moves.length == 9) {
            return "Draw";
        } else {
            return "Pending";
        }
    }

    private boolean isWinner(char[][] grid, char player) {
        // Check rows
        for (int i = 0; i < 3; i++) {
            if (grid[i][0] == player && grid[i][1] == player && grid[i][2] == player) {
                return true;
            }
        }
        // Check columns
        for (int i = 0; i < 3; i++) {
            if (grid[0][i] == player && grid[1][i] == player && grid[2][i] == player) {
                return true;
            }
        }
        // Check diagonals
        if (grid[0][0] == player && grid[1][1] == player && grid[2][2] == player) {
            return true;
        }
        if (grid[0][2] == player && grid[1][1] == player && grid[2][0] == player) {
            return true;
        }
        return false;
    }
}
```
### 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".

## Optimized Counting of Rows, Columns, and Diagonals
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.
**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.
**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.
### Explanation
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".

```java
class Solution {
    public String tictactoe(int[][] moves) {
        int[] rows = new int[3];
        int[] cols = new int[3];
        int diag1 = 0;
        int diag2 = 0;
        int player = 1; // 1 for A, -1 for B

        for (int i = 0; i < moves.length; i++) {
            int r = moves[i][0];
            int c = moves[i][1];

            rows[r] += player;
            cols[c] += player;
            if (r == c) {
                diag1 += player;
            }
            if (r + c == 2) {
                diag2 += player;
            }

            // Check for winner
            if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3 ||
                Math.abs(diag1) == 3 || Math.abs(diag2) == 3) {
                return player == 1 ? "A" : "B";
            }

            // Switch player
            player *= -1;
        }

        // No winner yet, check for Draw or Pending
        return moves.length == 9 ? "Draw" : "Pending";
    }
}
```
### 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".

# Solutions
### Java

```java
class Solution {
public
  String tictactoe(int[][] moves) {
    int n = moves.length;
    int[] cnt = new int[8];
    for (int k = n - 1; k >= 0; k -= 2) {
      int i = moves[k][0], j = 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) {
        return k % 2 == 0 ? "A" : "B";
      }
    }
    return n == 9 ? "Draw" : "Pending";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string tictactoe(vector<vector<int>> &moves) {
    int n = moves.size();
    int cnt[8]{};
    for (int k = n - 1; k >= 0; k -= 2) {
      int i = moves[k][0], j = 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) {
        return k % 2 == 0 ? "A" : "B";
      }
    }
    return n == 9 ? "Draw" : "Pending";
  }
};

```

### Python

```python
class Solution:
    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"

```