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

Comments

[algorhymer]

Nice quickie. I gave it a like!

You could reframe it to be more honest too!

"""
Hi young one!
Good to see you!
Tip of the day:
Analyze the problem statement carefully... then do a really dirty cheat waaaay back from MS-DOS era Hahahha!

So the clean theoretical non-cringe part is:
Look at what you are doing with the naive solution! Think about it!
What you are really counting is set cardinality in this specific problem class.

The dirty bug ready senior-cringe trick is:
ATTENTION: Only do this if it is 100% your caller knows what she's doing!!!!_
Represent two players a +1 and -1 XD
Yeah :) It is a facepalmy extra dirty engineering trick. Yeah yeah.
But you know... sometimes we have to do these kind of things to gain performance.
We've been doing this sort of mental wtfs since punchcards XD

Of course... these sort of tricks... led to an outage at Cloudflare.
So be careful with dirty cheats! ;)
At least document to later generations when you bake into the code really dodgy assumptions!
Also, consult with QA too. Hehe.
Remember: It is a team effort. Large team effort.
People who think they are rockstars end up crashing prod or leave behind a mess that later generations have to work around.
We are all: humans :)

There's one single thing which differentiates SeniorDevs from JuniorDevs:
The prefix that MBA management hands out XD
Good luck on your journey young one!
Please fix all the bugs and finish all the things we weren't able to do due to crunch!
Now it is your generation's task to keep prod alive!
"""