# 1275. Find Winner on a Tic Tac Toe Game

Question Link is here.

This is a daily challenge problem. And this is the hardest easy-level problem that I ever encountered.

The the moves list provides us with the position that both player places, and problem wants us to find who wins at the end.

It's obvious that using brute force is not the desired solution, so we need to find a better solution.

My idea is, to win, there must be three same characters in the same row or same column or in the diagonal or the anti-diagonal. Therefore, we can use some variables to store the state of each row, each column, diagnoal and anti-diagnoal in the 3*3 grid. So, we use 1 to indicate player1 and -1 to indicate player2. By doing this, if the sum of a row or a column or diag/anti-diag equals 3 or -3, we would know the current player already wins.

Therefore, the solution is shown below.

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        row = [0 for i in range(3)] #row indicator
        col = [0 for i in range(3)] #col indicator
        diag = 0 #diagnoal sum
        antiDiag = 0 #anti-diagnoal sum
        current = 1
        for x, y in moves:
            row[x] += current
            col[y] += current
            if x == y:
                diag += current
            if x + y == 2:
                antiDiag += current
            if abs(row[x]) == 3 or abs(col[y]) == 3 or abs(diag) == 3 or abs(antiDiag) == 3:
                if current == 1:
                    return 'A'
                else:
                    return "B"
            current *= -1
        if len(moves) == 9:
            return "Draw"
        else:
            return "Pending"

This solution has Time complexity of $O(n)$.