Find Winner on a Tic Tac Toe Game

easy math simulation

Problem

Given a sequence of moves on a 3×3 board (player A goes first, then B, alternating), return "A", "B", "Draw", or "Pending". Use signed counters (+1 for A, −1 for B) on each row, column, and the two diagonals; a |value| of 3 means a win.

Inputmoves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

Output"A"

A plays (0,0),(1,1),(2,2) — main diagonal.

moves (e.g. 0,0;2,0;1,1;2,1;2,2)

def tictactoe(moves):
    rows = [0, 0, 0]
    cols = [0, 0, 0]
    diag = anti = 0
    for k, (r, c) in enumerate(moves):
        v = 1 if k % 2 == 0 else -1
        rows[r] += v
        cols[c] += v
        if r == c: diag += v
        if r + c == 2: anti += v
        if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti) == 3:
            return "A" if v == 1 else "B"
    return "Draw" if len(moves) == 9 else "Pending"

function tictactoe(moves) {
  const rows = [0, 0, 0], cols = [0, 0, 0];
  let diag = 0, anti = 0;
  for (let k = 0; k < moves.length; k++) {
    const [r, c] = moves[k];
    const v = k % 2 === 0 ? 1 : -1;
    rows[r] += v; cols[c] += v;
    if (r === c) diag += v;
    if (r + c === 2) anti += v;
    if (Math.abs(rows[r]) === 3 || Math.abs(cols[c]) === 3 ||
        Math.abs(diag) === 3 || Math.abs(anti) === 3) {
      return v === 1 ? "A" : "B";
    }
  }
  return moves.length === 9 ? "Draw" : "Pending";
}

class Solution {
    public String tictactoe(int[][] moves) {
        int[] rows = new int[3], cols = new int[3];
        int diag = 0, anti = 0;
        for (int k = 0; k < moves.length; k++) {
            int r = moves[k][0], c = moves[k][1];
            int v = (k % 2 == 0) ? 1 : -1;
            rows[r] += v; cols[c] += v;
            if (r == c) diag += v;
            if (r + c == 2) anti += v;
            if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3
                    || Math.abs(diag) == 3 || Math.abs(anti) == 3) {
                return v == 1 ? "A" : "B";
            }
        }
        return moves.length == 9 ? "Draw" : "Pending";
    }
}

string tictactoe(vector<vector<int>>& moves) {
    int rows[3] = {}, cols[3] = {};
    int diag = 0, anti = 0;
    for (int k = 0; k < (int)moves.size(); k++) {
        int r = moves[k][0], c = moves[k][1];
        int v = (k % 2 == 0) ? 1 : -1;
        rows[r] += v; cols[c] += v;
        if (r == c) diag += v;
        if (r + c == 2) anti += v;
        if (abs(rows[r]) == 3 || abs(cols[c]) == 3
                || abs(diag) == 3 || abs(anti) == 3) {
            return v == 1 ? "A" : "B";
        }
    }
    return moves.size() == 9 ? "Draw" : "Pending";
}

Explanation

Instead of scanning the whole 3×3 board after every move, this solution keeps a handful of running counters and updates them as each move comes in. That makes checking for a win instant.

The clever trick is using signed numbers: player A adds +1 and player B adds -1 to whatever line a move touches. We keep one counter per row (rows), one per column (cols), one for the main diagonal (diag), and one for the anti-diagonal (anti). If any of these reaches +3 or -3, that line is filled by a single player, so someone has won.

For each move at (r, c) we add v to rows[r] and cols[c]. If r == c the cell is on the main diagonal, and if r + c == 2 it is on the anti-diagonal, so we update those too. Then we just check whether any counter hit an absolute value of 3.

Example: A plays (0,0), (1,1), (2,2) — all on the main diagonal. Each adds +1, so diag becomes 3 and A is declared the winner.

If we finish all moves with no winner, the result is "Draw" when all 9 cells are filled, otherwise "Pending" because the game is not over yet.

Time: O(m) for m moves Space: O(1)