Java LLD: Design Tic-Tac-Toe with O(1) Win Detection

Java LLD: Design Tic-Tac-Toe with O(1) Win Detection

Designing Tic-Tac-Toe is a classic Low-Level Design (LLD) interview question used by companies like Microsoft and Amazon to evaluate clean code and algorithmic efficiency. While the rules are simple, writing a scalable, maintainable, and highly performant solution separates senior engineers from juniors.

The Mistake Most Candidates Make

• Scanning the entire board: Iterating through a 2D array to check rows, columns, and diagonals after every single move ($O(N^2)$ or $O(N)$ time complexity).
• Violating SOLID SRP: Mixing game state, board representation, and win-checking logic inside a single bloated Game class.
• Hardcoding dimensions: Writing logic restricted to a $3 \times 3$ grid, making it impossible to scale to an $N \times N$ board or swap winning rules.

The Right Approach

• Core mental model: Represent players as mathematical weights (+1 and -1) to track state changes dynamically.
• Key entities: Game, Board, Player, WinningStrategy.
• Why it beats the naive approach: It achieves $O(1)$ win detection and decouples the evaluation logic from the physical board representation.

Heads up: if you want to see these patterns applied to real interview problems, javalld.com has full machine coding solutions with traces.

The Key Insight (Code)

public class SumArrayWinStrategy {
    private final int[] rows, cols;
    private int diag, antiDiag, N;

    public boolean makeMoveAndCheckWin(int r, int c, int val) { // val is +1 or -1
        rows[r] += val;
        cols[c] += val;
        if (r == c) diag += val;
        if (r + c == N - 1) antiDiag += val;

        return Math.abs(rows[r]) == N || Math.abs(cols[c]) == N 
            || Math.abs(diag) == N || Math.abs(antiDiag) == N;
    }
}

Key Takeaways

• O(1) Win Detection: By mapping Player 1 to +1 and Player 2 to -1, we track row, column, and diagonal sums to detect a win instantly without scanning the board.
• SOLID SRP: Decouple the game loop (Game) from the win evaluation logic (WinningStrategy) to make code highly maintainable.
• Strategy Pattern: Encapsulate the win-checking algorithm so you can easily switch from standard Tic-Tac-Toe to custom variants (e.g., Wild Tic-Tac-Toe) without changing the Board class.

Full working implementation with execution trace available at https://javalld.com/problems/tictactoe