Sum-Array Win Detection

Sum-Array Win Detection

What is it? (The Analogy)

Imagine you are keeping score in a basketball game. Every time a team scores, you add points

to their running total. At any moment, a coach can yell "What is the score?" and you instantly

answer because you have been keeping a running total the whole time. You never have to go

back and re-add every single basket from the beginning of the game.

Now imagine a slightly different game: Tic-Tac-Toe on steroids. Instead of a tiny 3x3

board, picture a huge NxN board. After every move, you need to check: "Did someone just win?"

A win happens when an entire row, an entire column, or an entire diagonal is filled by one

player. If you checked every cell in the row every single time, that would be painfully slow

on a 1000x1000 board.

The Sum-Array Win Detection trick is this: instead of scanning every cell, you keep a

running counter for each row, each column, and each diagonal. When Player X places a

piece, you add +1 to that row's counter, that column's counter, and (if applicable) the

diagonal counter. When Player O places a piece, you add -1. If any counter ever reaches

+N or -N, someone just won! You detect it instantly in O(1) time.

Why do we need it?

The Brute Force Problem

Let's say we have an NxN board. After every move, we want to check if the current player

won. The naive approach:

1// BRUTE FORCE: Check entire row, column, and diagonals
2boolean checkWin(char[][] board, int row, int col, char player) {
3    int n = board.length;
4
5    // Check the entire row — O(N)
6    boolean rowWin = true;
7    for (int j = 0; j < n; j++) {
8        if (board[row][j] != player) { rowWin = false; break; }
9    }
10
11    // Check the entire column — O(N)
12    boolean colWin = true;
13    for (int i = 0; i < n; i++) {
14        if (board[i][col] != player) { colWin = false; break; }
15    }
16
17    // Check diagonals — O(N) each
18    // ... more loops ...
19
20    return rowWin || colWin || diagWin || antiDiagWin;
21}

Cost: Every single move triggers O(N) work. Over an entire game of N*N moves, that is

O(N^3) total work. On a 1000x1000 board, that is one billion operations. Ouch.

The Better Way: Running Counters

What if we never look at the board at all? Instead, we maintain:

• An array rowSum[N] — one counter per row
• An array colSum[N] — one counter per column
• A single variable diagSum — for the main diagonal (top-left to bottom-right)
• A single variable antiDiagSum — for the anti-diagonal (top-right to bottom-left)

Each move updates at most 4 numbers and checks at most 4 conditions. That is O(1)!

How it works — Step by Step

1. Initialize all counters to 0.
2. On each move at position (row, col) by a player:

- Determine the increment: +1 for Player 1, -1 for Player 2.

- Add the increment to rowSum[row].

- Add the increment to colSum[col].

- If row == col, add the increment to diagSum (main diagonal).

- If row + col == N - 1, add the increment to antiDiagSum (anti-diagonal).

1. Check for win: If the absolute value of any of these four counters equals N,

the current player has won!

1. Return the winner, or indicate no winner yet.

Let's Build It Together

Let's build a Tic-Tac-Toe win detector for an NxN board. We will use a fun school scenario:

two students, Alice and Bob, are playing on a giant board during recess.

1/**
2 * TicTacToe Win Detector using Sum-Array technique.
3 *
4 * Alice is Player 1 (+1), Bob is Player 2 (-1).
5 * We detect a win in O(1) per move instead of O(N).
6 */
7public class TicTacToe {
8
9    private int[] rowSum;      // Running total for each row
10    private int[] colSum;      // Running total for each column
11    private int diagSum;       // Running total for main diagonal
12    private int antiDiagSum;   // Running total for anti-diagonal
13    private int n;             // Board size
14
15    /**
16     * Step 1: Set up counters — all start at zero.
17     * Think of it like resetting the scoreboard before a new game.
18     */
19    public TicTacToe(int n) {
20        this.n = n;
21        this.rowSum = new int[n];       // All zeros by default
22        this.colSum = new int[n];       // All zeros by default
23        this.diagSum = 0;
24        this.antiDiagSum = 0;
25    }
26
27    /**
28     * Step 2: A player makes a move.
29     *
30     * @param row    the row index (0-based)
31     * @param col    the column index (0-based)
32     * @param player 1 for Alice, 2 for Bob
33     * @return 0 if no winner yet, 1 if Alice wins, 2 if Bob wins
34     */
35    public int move(int row, int col, int player) {
36        // Alice gets +1, Bob gets -1
37        // This is the MAGIC — opposite signs let one counter track both players
38        int increment = (player == 1) ? 1 : -1;
39
40        // Update the running totals — O(1) work!
41        rowSum[row] += increment;
42        colSum[col] += increment;
43
44        // Only update diagonal if this cell is ON the diagonal
45        if (row == col) {
46            diagSum += increment;
47        }
48
49        // Only update anti-diagonal if this cell is ON the anti-diagonal
50        // For a 3x3 board: positions (0,2), (1,1), (2,0) satisfy row+col == 2
51        if (row + col == n - 1) {
52            antiDiagSum += increment;
53        }
54
55        // Step 3: Check for a win — did any counter reach +N or -N?
56        if (Math.abs(rowSum[row]) == n ||
57            Math.abs(colSum[col]) == n ||
58            Math.abs(diagSum) == n ||
59            Math.abs(antiDiagSum) == n) {
60            return player;  // This player just won!
61        }
62
63        return 0;  // No winner yet — game continues
64    }
65}

Usage example:

1public class RecessGame {
2    public static void main(String[] args) {
3        TicTacToe game = new TicTacToe(3);
4
5        // Alice and Bob take turns
6        System.out.println(game.move(0, 0, 1));  // Alice -> 0 (no winner)
7        System.out.println(game.move(1, 1, 2));  // Bob   -> 0
8        System.out.println(game.move(0, 1, 1));  // Alice -> 0
9        System.out.println(game.move(1, 0, 2));  // Bob   -> 0
10        System.out.println(game.move(0, 2, 1));  // Alice -> 1 (Alice wins! Row 0 is full)
11    }
12}

Dry Run / Trace

Let's trace through the game above on a 3x3 board (N=3).

Initial state:

rowSum = [0, 0, 0]    colSum = [0, 0, 0]    diagSum = 0    antiDiagSum = 0

Move 1: Alice (player=1) at (0, 0) — increment = +1

rowSum[0] += 1  =>  rowSum = [1, 0, 0]
colSum[0] += 1  =>  colSum = [1, 0, 0]
row == col (0==0), so diagSum += 1  =>  diagSum = 1
row + col = 0 != 2, skip antiDiagSum
Check: |1| != 3, |1| != 3, |1| != 3  =>  No winner. Return 0.

Move 2: Bob (player=2) at (1, 1) — increment = -1

rowSum[1] += -1  =>  rowSum = [1, -1, 0]
colSum[1] += -1  =>  colSum = [1, -1, 0]
row == col (1==1), so diagSum += -1  =>  diagSum = 0
row + col = 2 == 2, so antiDiagSum += -1  =>  antiDiagSum = -1
Check: |-1| != 3, |-1| != 3, |0| != 3, |-1| != 3  =>  No winner. Return 0.

Move 3: Alice (player=1) at (0, 1) — increment = +1

rowSum[0] += 1  =>  rowSum = [2, -1, 0]
colSum[1] += 1  =>  colSum = [1, 0, 0]
row != col (0 != 1), skip diagSum
row + col = 1 != 2, skip antiDiagSum
Check: |2| != 3, |0| != 3  =>  No winner. Return 0.

Move 4: Bob (player=2) at (1, 0) — increment = -1

rowSum[1] += -1  =>  rowSum = [2, -2, 0]
colSum[0] += -1  =>  colSum = [0, 0, 0]
row != col (1 != 0), skip diagSum
row + col = 1 != 2, skip antiDiagSum
Check: |-2| != 3, |0| != 3  =>  No winner. Return 0.

Move 5: Alice (player=1) at (0, 2) — increment = +1

rowSum[0] += 1  =>  rowSum = [3, -2, 0]
colSum[2] += 1  =>  colSum = [0, 0, 1]
row != col (0 != 2), skip diagSum
row + col = 2 == 2, so antiDiagSum += 1  =>  antiDiagSum = 0
Check: |3| == 3  =>  WINNER! Return 1 (Alice wins!)

Time & Space Complexity

• Time per move: O(1) — we do exactly 4 additions and 4 comparisons, regardless of board size.
• Space: O(N) — two arrays of size N, plus two integer variables. This is negligible.
• Why it is better: On a 1000x1000 board, brute force does ~4000 operations per move.

Sum-array does exactly 8. That is a 500x speedup.

Common Mistakes & Gotchas

• Forgetting the anti-diagonal condition. The main diagonal is row == col. The

anti-diagonal is row + col == N - 1. Many people forget the second one.

• Using 0 and 1 instead of +1 and -1. If both players add positive values, you cannot

distinguish who filled a line. The +1/-1 trick is essential.

• Off-by-one on the anti-diagonal. It is N - 1, not N. For a 3x3 board, the

anti-diagonal cells are at (0,2), (1,1), (2,0) — all sum to 2, which is 3-1.

• Not handling the center cell on odd-sized boards. The center cell (e.g., (1,1) on a

3x3 board) lies on BOTH diagonals. Make sure to update both diagSum and antiDiagSum.

• Checking only the row or only the column. You must check all four: row, column,

main diagonal, and anti-diagonal.

Interview Tip

Quick Quiz

1. Think about it: What happens if a cell that already has a piece is overwritten?

How would you handle "undo" moves? (Hint: subtract the increment.)

1. Extend it: What if the game allows a win with K-in-a-row on an NxN board (where

K < N)? Can the sum-array approach still work, or do you need a different technique?

1. Edge case: On a 1x1 board, the very first move should be a win. Does our algorithm

handle this correctly? Trace through it mentally.

Summary — Key Takeaways

• Running counters eliminate repeated scanning. Instead of checking N cells on every

move, maintain a sum and check one number.

• The +1/-1 encoding lets a single counter track two players. A full line by one player

yields +N or -N; a mixed line never reaches those extremes.

• O(1) per move, O(N) space — an excellent trade-off for any grid-based win-detection

problem.

• This pattern appears everywhere — not just Tic-Tac-Toe, but Connect-4 variants,

Gomoku, and any "fill a line" game in LLD interviews.