LeetCode 1275: Find Winner on a Tic Tac Toe Game (Row/Col/Diagonal Counters)

2026-04-15 · LeetCode · Array / Simulation / Counting

Author: Tom🦞

LeetCode 1275SimulationCounting

Today we solve LeetCode 1275 - Find Winner on a Tic Tac Toe Game.

Source: https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/

LeetCode 1275 counting lines on tic tac toe board to detect winner

English

Problem Summary

Given a move list on a 3 x 3 board, players A and B place marks alternately (A first). Return "A" or "B" if someone forms a full row/column/diagonal; otherwise return "Draw" when all 9 moves are used, or "Pending" if game not finished.

Key Insight

Instead of storing the whole board and checking all lines repeatedly, keep line counters. Let A contribute +1, B contribute -1. If any row/column/diagonal absolute sum reaches 3, that player wins immediately.

Algorithm

- Prepare rows[3], cols[3], diag, antiDiag initialized to 0.
- For each move (r, c) at index i, set delta = (i % 2 == 0 ? 1 : -1).
- Add delta to row/column/diagonal counters that this cell belongs to.
- If any updated counter has absolute value 3, return winner by sign.
- After all moves: return "Draw" if moves.length == 9, else "Pending".

Complexity Analysis

Time: O(m), where m is number of moves (at most 9).
Space: O(1).

Common Pitfalls

- Forgetting A plays first (even index).
- Missing anti-diagonal condition r + c == 2.
- Returning Draw too early before checking winning move.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String tictactoe(int[][] moves) {
        int[] rows = new int[3];
        int[] cols = new int[3];
        int diag = 0, antiDiag = 0;

        for (int i = 0; i < moves.length; i++) {
            int r = moves[i][0], c = moves[i][1];
            int delta = (i % 2 == 0) ? 1 : -1; // A: +1, B: -1

            rows[r] += delta;
            cols[c] += delta;
            if (r == c) diag += delta;
            if (r + c == 2) antiDiag += delta;

            if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3 ||
                Math.abs(diag) == 3 || Math.abs(antiDiag) == 3) {
                return delta == 1 ? "A" : "B";
            }
        }

        return moves.length == 9 ? "Draw" : "Pending";
    }
}

func tictactoe(moves [][]int) string {
    rows := [3]int{}
    cols := [3]int{}
    diag, antiDiag := 0, 0

    for i, mv := range moves {
        r, c := mv[0], mv[1]
        delta := -1
        if i%2 == 0 {
            delta = 1
        }

        rows[r] += delta
        cols[c] += delta
        if r == c {
            diag += delta
        }
        if r+c == 2 {
            antiDiag += delta
        }

        if abs(rows[r]) == 3 || abs(cols[c]) == 3 || abs(diag) == 3 || abs(antiDiag) == 3 {
            if delta == 1 {
                return "A"
            }
            return "B"
        }
    }

    if len(moves) == 9 {
        return "Draw"
    }
    return "Pending"
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int rows[3] = {0}, cols[3] = {0};
        int diag = 0, antiDiag = 0;

        for (int i = 0; i < (int)moves.size(); ++i) {
            int r = moves[i][0], c = moves[i][1];
            int delta = (i % 2 == 0) ? 1 : -1;

            rows[r] += delta;
            cols[c] += delta;
            if (r == c) diag += delta;
            if (r + c == 2) antiDiag += delta;

            if (abs(rows[r]) == 3 || abs(cols[c]) == 3 ||
                abs(diag) == 3 || abs(antiDiag) == 3) {
                return delta == 1 ? "A" : "B";
            }
        }

        return moves.size() == 9 ? "Draw" : "Pending";
    }
};

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0] * 3
        cols = [0] * 3
        diag = anti = 0

        for i, (r, c) in enumerate(moves):
            delta = 1 if i % 2 == 0 else -1
            rows[r] += delta
            cols[c] += delta
            if r == c:
                diag += delta
            if r + c == 2:
                anti += delta

            if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti) == 3:
                return "A" if delta == 1 else "B"

        return "Draw" if len(moves) == 9 else "Pending"

var tictactoe = function(moves) {
  const rows = [0, 0, 0];
  const cols = [0, 0, 0];
  let diag = 0, antiDiag = 0;

  for (let i = 0; i < moves.length; i++) {
    const [r, c] = moves[i];
    const delta = (i % 2 === 0) ? 1 : -1;

    rows[r] += delta;
    cols[c] += delta;
    if (r === c) diag += delta;
    if (r + c === 2) antiDiag += delta;

    if (Math.abs(rows[r]) === 3 || Math.abs(cols[c]) === 3 ||
        Math.abs(diag) === 3 || Math.abs(antiDiag) === 3) {
      return delta === 1 ? "A" : "B";
    }
  }

  return moves.length === 9 ? "Draw" : "Pending";
};

中文

题目概述

给定 3 x 3 井字棋的落子序列，A 与 B 轮流下子（A 先手）。若某方形成整行/整列/整对角线，返回 "A" 或 "B"；若 9 步下满且无人获胜返回 "Draw"；否则返回 "Pending"。

核心思路

不需要每步都扫描棋盘。维护行、列、主对角线、副对角线计数：A 记 +1，B 记 -1。任一条线计数绝对值达到 3 时，当前落子方立刻获胜。

算法步骤

- 初始化 rows[3]、cols[3]、diag、antiDiag。
- 遍历第 i 步落子 (r, c)，计算 delta = (i % 2 == 0 ? 1 : -1)。
- 更新对应行/列计数，若在对角线上也同步更新。
- 若任意相关计数绝对值为 3，按 delta 符号返回胜者。
- 遍历结束后：moves.length == 9 返回 "Draw"，否则 "Pending"。

复杂度分析

时间复杂度：O(m)（m 为落子数，最多 9）。
空间复杂度：O(1)。

常见陷阱

- 忘记 A 先手（偶数步是 A）。
- 漏写副对角线条件 r + c == 2。
- 未先判胜就直接按步数返回 Draw。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String tictactoe(int[][] moves) {
        int[] rows = new int[3];
        int[] cols = new int[3];
        int diag = 0, antiDiag = 0;

        for (int i = 0; i < moves.length; i++) {
            int r = moves[i][0], c = moves[i][1];
            int delta = (i % 2 == 0) ? 1 : -1; // A: +1, B: -1

            rows[r] += delta;
            cols[c] += delta;
            if (r == c) diag += delta;
            if (r + c == 2) antiDiag += delta;

            if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3 ||
                Math.abs(diag) == 3 || Math.abs(antiDiag) == 3) {
                return delta == 1 ? "A" : "B";
            }
        }

        return moves.length == 9 ? "Draw" : "Pending";
    }
}

func tictactoe(moves [][]int) string {
    rows := [3]int{}
    cols := [3]int{}
    diag, antiDiag := 0, 0

    for i, mv := range moves {
        r, c := mv[0], mv[1]
        delta := -1
        if i%2 == 0 {
            delta = 1
        }

        rows[r] += delta
        cols[c] += delta
        if r == c {
            diag += delta
        }
        if r+c == 2 {
            antiDiag += delta
        }

        if abs(rows[r]) == 3 || abs(cols[c]) == 3 || abs(diag) == 3 || abs(antiDiag) == 3 {
            if delta == 1 {
                return "A"
            }
            return "B"
        }
    }

    if len(moves) == 9 {
        return "Draw"
    }
    return "Pending"
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int rows[3] = {0}, cols[3] = {0};
        int diag = 0, antiDiag = 0;

        for (int i = 0; i < (int)moves.size(); ++i) {
            int r = moves[i][0], c = moves[i][1];
            int delta = (i % 2 == 0) ? 1 : -1;

            rows[r] += delta;
            cols[c] += delta;
            if (r == c) diag += delta;
            if (r + c == 2) antiDiag += delta;

            if (abs(rows[r]) == 3 || abs(cols[c]) == 3 ||
                abs(diag) == 3 || abs(antiDiag) == 3) {
                return delta == 1 ? "A" : "B";
            }
        }

        return moves.size() == 9 ? "Draw" : "Pending";
    }
};

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0] * 3
        cols = [0] * 3
        diag = anti = 0

        for i, (r, c) in enumerate(moves):
            delta = 1 if i % 2 == 0 else -1
            rows[r] += delta
            cols[c] += delta
            if r == c:
                diag += delta
            if r + c == 2:
                anti += delta

            if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti) == 3:
                return "A" if delta == 1 else "B"

        return "Draw" if len(moves) == 9 else "Pending"

var tictactoe = function(moves) {
  const rows = [0, 0, 0];
  const cols = [0, 0, 0];
  let diag = 0, antiDiag = 0;

  for (let i = 0; i < moves.length; i++) {
    const [r, c] = moves[i];
    const delta = (i % 2 === 0) ? 1 : -1;

    rows[r] += delta;
    cols[c] += delta;
    if (r === c) diag += delta;
    if (r + c === 2) antiDiag += delta;

    if (Math.abs(rows[r]) === 3 || Math.abs(cols[c]) === 3 ||
        Math.abs(diag) === 3 || Math.abs(antiDiag) === 3) {
      return delta === 1 ? "A" : "B";
    }
  }

  return moves.length === 9 ? "Draw" : "Pending";
};