# 1275. Find Winner on a Tic Tac Toe Game

### Description

Tic-tac-toe is played by two players *A* and *B* on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

* 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 3 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 an array `moves` where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which *A* and *B* play.

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** (It follows the rules of Tic-Tac-Toe), the grid is initially empty and *A* will play **first**.

### Constraints

* `1 <= moves.length <= 9`
* `moves[i].length == 2`
* `0 <= moves[i][j] <= 2`
* There are no repeated elements on `moves`.
* `moves` follow the rules of tic tac toe.

### Approach

### Links

* Binarysearch
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** moves = \[\[0, 0], \[2, 0], \[1, 1], \[2, 1], \[2, 2]]

**Output:** "A"

**Explanation:** "A" wins, he always plays first.

<div align="left"><img src="/files/-Mk1eoiNeatnWQXvsPRs" alt=""></div>
{% endtab %}

{% tab title="Example 2" %}
**Input:** moves = \[\[0,0],\[1,1],\[0,1],\[0,2],\[1,0],\[2,0]]

**Output:** "B"

**Explanation:** "B" wins.

<div align="left"><img src="/files/-Mk1fGbH-pJJLuD3MP8t" alt=""></div>
{% endtab %}

{% tab title="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.

"XXO"

"OOX"

"XOX"
{% endtab %}

{% tab title="Example 4" %}
**Input:** moves = \[\[0,0],\[1,1]]

**Output:** "Pending"

**Explanation:** The game has not finished yet.

"X "

" O "

" "
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    
    public String tictactoe(int[][] moves) {
        if(moves.length > 4) {
            int n = 3;
            char[] players = {'A', 'B'};
            char[][] board = new char[n][n];
            for(int i = 0; i < moves.length; i++) {
                int[] move = moves[i];
                board[move[0]][move[1]] = players[i%2];
            }
        
            for(int i = 0; i < n; i++) {
                for(char player: players) {
                    if(rowCheck(board, i, player) || colCheck(board, i, player)) {
                        return player + "";
                    }
                }
            }

            for(char player: players) {
                if(diagonalCheck(board, player)) {
                    return player + "";
                }
            }
        }
        
        return moves.length == 9? "Draw": "Pending";
    }
    
    private boolean rowCheck(char[][] board, int row, char player) {
        return board[row][0] == player && board[row][1] == player && board[row][2] == player;
    }
    
    private boolean colCheck(char[][] board, int col, char player) {
        return board[0][col] == player && board[1][col] == player && board[2][col] == player;
    }
    
    private boolean diagonalCheck(char[][] board, char player) {
        return (board[0][0] == player && board[1][1] == player && board[2][2] == player) || 
            (board[2][0] == player && board[1][1] == player && board[0][2] == player);
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private final int n = 3;
    
    public String tictactoe(int[][] moves) {
        if(moves.length > 4) {
            int[] rows = new int[n];
            int[] cols = new int[n];
            int diagonal = 0, antiDiagonal = 0;
            
            int player = 1;
            
            for(int[] move: moves) {
                int x = move[0], y = move[1];
                
                if(x == y) {
                    diagonal += player;
                }
                if(x+y == n-1) {
                    antiDiagonal += player;
                }
                
                rows[x] += player;
                cols[y] += player;
                
                if(Math.abs(rows[x]) == n || Math.abs(cols[y]) == n ||
                   Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) {
                    return (player == 1)? "A": "B";
                }
                
                player *= -1;
            }
        }
        
        return moves.length == n*n? "Draw": "Pending";
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/1201-1300/find-winner-on-a-tic-tac-toe-game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.