O(1) Tic-Tac-Toe Win: Interview Prep You Need

You're probably thinking, "Tic-Tac-Toe? Seriously?" I get it. It sounds almost insulting, like they're testing if you can tie your shoes. But here's the thing: nailing the Tic-Tac-Toe win detection and doing it right – meaning O(1) time complexity – reveals a lot about your design intuition. It’s a common LLD (Low-Level Design) interview question, especially for new grads or junior roles, but also a killer warm-up for more complex systems. Bombing this simple one means you're probably not ready for a real system design discussion. This isn't about knowing the game; it’s about recognizing patterns, managing state, and optimizing for performance.

Beyond the Board: Why Tic-Tac-Toe Matters

Many candidates stumble here by immediately jumping to the obvious solution: iterating through rows, columns, and diagonals after every move. That's a perfectly functional O(N) or O(N^2) approach for an N x N board (or O(1) for a fixed 3x3, but that's cheating the spirit of the question). An interviewer isn't looking for "functional." They're looking for "optimal." They want to see if you can think past the brute force, if you can identify invariants and pre-calculate or incrementally update state. This simple game becomes a proxy for how you'd handle state management in a distributed system, or how you'd optimize a complex query in a database. It's about designing for scale, even when N is just 3.

The Naive Approach: A Dead End

Let's quickly dismiss the "check everything" method. You have a 3x3 board. After each move, you iterate:

1. Check all rows: Three iterations.
2. Check all columns: Three iterations.
3. Check both diagonals: Two iterations.

For each check, you're looking at three cells. So, roughly 8 * 3 = 24 cell accesses. This is constant for a 3x3 board. If the interviewer pushes for an N x N board, however, this quickly becomes O(N) for checking rows/columns (N rows, N columns, each check takes N steps) and O(N) for diagonals. That's acceptable for small N, but not optimal. And "optimal" is the word you need to be thinking about in interviews. Your goal is to detect a win in O(1) time, irrespective of the board size N.

The O(1) Insight: Incremental Updates

The key to O(1) win detection lies in recognizing that a win can only occur along the row, column, or diagonal where the last move was played. You don't need to re-evaluate the entire board. You only need to check the lines affected by the most recent placement.

This is still not O(1) for an N x N board if you simply iterate that specific row/column/diagonal. For O(1), you need to maintain auxiliary data structures that get updated with each move. Think counters. When a player marks a cell, they increment a counter for that row, that column, and potentially a diagonal.

Here's the breakdown:

• Row Counters: An array rows[N] for Player X, and another rows[N] for Player O. rows[i] stores how many cells Player X (or O) has marked in row i.
• Column Counters: Similarly, cols[N] for Player X and cols[N] for Player O. cols[j] stores how many cells Player X (or O) has marked in column j.
• Diagonal Counters: Two counters for each player: one for the main diagonal (where row == col) and one for the anti-diagonal (where row + col == N - 1).

When a player makes a move at (r, c):

1. Increment rows[r] for that player.
2. Increment cols[c] for that player.
3. If r == c, increment the main diagonal counter for that player.
4. If r + c == N - 1, increment the anti-diagonal counter for that player.

After each increment, you check if any of these counters have reached N. If rows[r] == N, that player wins. If cols[c] == N, they win. Same for the diagonal counters. All these operations are constant time. Array lookups, increments, and comparisons – pure O(1).

Designing the Game Class

Okay, let's put this into a TicTacToe class. You'll need a constructor, a move method, and perhaps a way to query the current board state (though for win detection, it's not strictly necessary).

public class TicTacToe {
    private int[] rowsX; // Counters for player X's marks in each row
    private int[] colsX; // Counters for player X's marks in each column
    private int diagX;   // Counter for player X's marks in main diagonal
    private int antiDiagX; // Counter for player X's marks in anti-diagonal

    private int[] rowsO; // Counters for player O's marks in each row
    private int[] colsO; // Counters for player O's marks in each column
    private int diagO;   // Counter for player O's marks in main diagonal
    private int antiDiagO; // Counter for player O's marks in anti-diagonal

    private int n; // Size of the board

    public TicTacToe(int n) {
        this.n = n;
        rowsX = new int[n];
        colsX = new int[n];
        rowsO = new int[n];
        colsO = new int[n];
        diagX = 0;
        antiDiagX = 0;
        diagO = 0;
        antiDiagO = 0;
    }

    /**
     * Makes a move for a given player at (row, col)
     * @param row The row (0-indexed)
     * @param col The column (0-indexed)
     * @param player The player making the move (1 for X, 2 for O)
     * @return 0 if no winner, 1 if player X wins, 2 if player O wins.
     */
    public int move(int row, int col, int player) {
        if (player == 1) { // Player X
            rowsX[row]++;
            colsX[col]++;
            if (row == col) {
                diagX++;
            }
            if (row + col == n - 1) {
                antiDiagX++;
            }

            if (rowsX[row] == n || colsX[col] == n || diagX == n || antiDiagX == n) {
                return 1; // Player X wins
            }
        } else { // Player O
            rowsO[row]++;
            colsO[col]++;
            if (row == col) {
                diagO++;
            }
            if (row + col == n - 1) {
                antiDiagO++;
            }

            if (rowsO[row] == n || colsO[col] == n || diagO == n || antiDiagO == n) {
                return 2; // Player O wins
            }
        }
        return 0; // No winner yet
    }
}

This code snippet is a pretty standard way to implement the O(1) win detection. It’s clean, efficient, and directly addresses the prompt.

Initializing and Edge Cases

What about initialization? The constructor handles it by setting all counters to zero. That's crucial. What if n=1? A 1x1 board. The first move wins. My code handles that: rowsX[0] becomes 1, n is 1, so rowsX[0] == n is true. Same for diagonals. It works.

What about invalid moves? Like placing on an already occupied cell or out of bounds? This design doesn't explicitly prevent that. You'd typically add checks in a real game:

• Bounds Check: if (row < 0 || row >= n || col < 0 || col >= n)
• Occupied Cell Check: You'd need a board[N][N] array to track cell occupancy. If board[row][col] != EMPTY, then it's an invalid move. This board array isn't strictly necessary for O(1) win detection, but it's essential for a functional game. Your interviewer might ask you to add it.

This brings up an important point: clarify assumptions. Before you write a line of code, ask: "Are we assuming valid moves are always provided, or should I handle invalid inputs?" This demonstrates thoughtfulness.

Memory and Time Complexity Revisited

Let's solidify the complexity analysis for this design.

• Time Complexity of move() method:

  • Array lookups (rowsX[row], colsX[col], etc.): O(1)
  • Increments: O(1)
  • Comparisons: O(1)
  • Conditional checks: O(1)
  • Total: O(1) per move. This is exactly what we aimed for.

• Space Complexity:

  • rowsX, colsX, rowsO, colsO arrays: each of size N. So, 4 * N integers.
  • diagX, antiDiagX, diagO, antiDiagO integers: constant space.
  • Total: O(N). This is a trade-off. We achieved O(1) time by using O(N) space to store auxiliary counters. This is a common pattern in optimization.

An interviewer might ask about this trade-off. Be ready to explain it. "We're using linear space to achieve constant time win detection. For large N, this space usage might be a concern, but it's usually acceptable given typical board sizes for a Tic-Tac-Toe variant and the performance gains."

Alternative Implementations and Considerations

Single Counter Array for Players

You could combine the player counters into a single set of arrays. Instead of rowsX and rowsO, you could have rows[N] where a positive value means Player 1 has that many marks, and a negative value means Player 2 has that many marks.

public class TicTacToeUnified {
    private int[] rows;
    private int[] cols;
    private int diag;
    private int antiDiag;
    private int n;

    public TicTacToeUnified(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
        diag = 0;
        antiDiag = 0;
    }

    public int move(int row, int col, int player) {
        int playerValue = (player == 1) ? 1 : -1; // X adds 1, O adds -1

        rows[row] += playerValue;
        cols[col] += playerValue;

        if (row == col) {
            diag += playerValue;
        }
        if (row + col == n - 1) {
            antiDiag += playerValue;
        }

        // Check for win
        // Player X wins if counter reaches N
        // Player O wins if counter reaches -N
        if (Math.abs(rows[row]) == n ||
            Math.abs(cols[col]) == n ||
            Math.abs(diag) == n ||
            Math.abs(antiDiag) == n) {
            return player; // The current player wins
        }
        return 0; // No winner yet
    }
}

This approach is slightly more compact and uses less memory (2 * N integers for rows/cols instead of 4 * N, plus 2 integers for diagonals instead of 4). It's a neat trick. The logic remains O(1) time and O(N) space. This shows a bit more creativity and optimization. It's a good one to mention if you have extra time or if the interviewer nudges you towards memory efficiency.

Handling a Draw

The current win detection logic only returns a winner. What if the board fills up and no one wins? That's a draw. To detect this, you'd need another counter: movesMade. Increment it after every valid move. If movesMade == n * n and no winner has been declared, it's a draw.

// Inside TicTacToe class
private int movesMade;

public TicTacToe(int n) {
    // ... existing initialization ...
    movesMade = 0;
}

public int move(int row, int col, int player) {
    // ... existing win detection logic ...

    // After a valid move and no winner yet:
    movesMade++;
    if (movesMade == n * n) {
        return -1; // Indicate a draw
    }

    return 0; // No winner, no draw yet
}

You'd need to update the return type or add an enum for move to clearly distinguish between no winner, player X wins, player O wins, and a draw. Something like enum GameState { ONGOING, PLAYER_X_WINS, PLAYER_O_WINS, DRAW }. This adds robustness to the design.

What if the game needs to be reset?

This is a common follow-up. How do you reset? You simply create a new TicTacToe instance. The current design is stateless apart from the counters. If you were tracking the actual board cells, you'd need to clear that too.

// If you added a board to track occupied cells for invalid move checks:
private int[][] board; // e.g., 0 for empty, 1 for X, 2 for O

public TicTacToe(int n) {
    // ... existing counter initialization ...
    this.board = new int[n][n]; // All cells initialized to 0 (empty)
}

public int move(int row, int col, int player) {
    // First, check if move is valid
    if (board[row][col] != 0) { // Cell already taken
        throw new IllegalArgumentException("Cell (" + row + ", " + col + ") is already occupied.");
    }
    // ... rest of the logic ...
    board[row][col] = player; // Mark the cell
    // ...
}

Adding the board array increases space complexity to O(N^2) but is necessary for a fully functional game with move validation. The O(1) win detection itself remains O(N) space using just the counters. This is a nuanced point; be prepared to discuss it.

When O(1) isn't the whole story: Caveats

Sometimes, an interviewer focuses so much on O(1) that you forget practical constraints. What if N is ridiculously huge, like 10^9? Then your O(N) space complexity for the counters (4 arrays of 10^9 integers) becomes a problem. That's gigabytes of memory just for counters.

In such an extreme case, you'd likely discuss alternative strategies, perhaps using a HashMap<Integer, Integer> for rows and cols counters, mapping row/column indices to counts. This would make space complexity O(M) where M is the number of moves made (at most N*N, but sparse if few moves). However, HashMap operations are average O(1) but worst-case O(N), so you lose the strict O(1) guarantee. This is a classic trade-off: space vs. time, and average vs. worst-case performance.

For typical interview scenarios and reasonable N (say, up to 1000), the O(N) space for arrays is perfectly acceptable and the strict O(1) time is preferred. Always clarify constraints on N. If they don't give one, assume N is small enough that O(N) space is fine.

Communication is Key

Remember, the interview isn't just about the code. It's about your thought process.

1. Start with the naive approach: Explain it, analyze it, and point out its shortcomings (especially for N x N). This shows you understand the problem and can identify inefficient solutions.
2. Propose the optimized approach: Explain the core idea (incremental updates, counters).
3. Detail the data structures: Walk through how each counter works.
4. Write the code: Cleanly, methodically.
5. Test with examples: A quick dry run with a simple 3x3 board.
6. Analyze complexity: Time and space for both the naive and your optimal solution.
7. Discuss trade-offs and edge cases: N=1, invalid moves, draw conditions, larger N considerations.

This structured approach shows you're not just coding, you're designing. That's what senior engineers do. Practicing this exact flow with a simple problem like Tic-Tac-Toe builds muscle memory for harder LLD and system design questions.

Final Thoughts

The Tic-Tac-Toe LLD problem, particularly the O(1) win detection, is deceptively simple. It tests your ability to optimize, manage state, and think about performance from the ground up, not just for a fixed 3x3 board but for a general N x N case. Get this one right, and you demonstrate a solid foundational understanding of data structures, algorithms, and thoughtful system design. Don't underestimate this "simple" game; mastering it means you're thinking like an engineer who consistently ships high-performing code.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep