Practice/Meta/Leetcode 348. Design Tic-Tac-Toe

Leetcode 348. Design Tic-Tac-Toe

CodingMust

Problem

Design a game board system for a two-player Connect-Four style game on an n×n grid. Your implementation should support placing game pieces and instantly determine if a player has achieved victory.

Create a class that initializes a square board of size n and provides a method to process moves. When a player places a piece at a specific position, your system must immediately check if that move completes a winning line (horizontal, vertical, or diagonal) and return the winning player number, or 0 if the game continues.

The critical design challenge is to achieve O(1) time complexity for each move operation. You cannot afford to scan the entire board after every move.

Requirements

1. Implement a ConnectFourBoard class that takes board size n in the constructor

2. Implement a make_move(row, col, player) method that:

   • Records the move at position (row, col) for the specified player
   • Returns the player number (1 or 2) if this move creates a winning line
   • Returns 0 if the game should continue

3. A winning line is formed when a player occupies all n positions in any row, column, or diagonal

4. Each move must be processed in O(1) time

5. You can assume all moves are valid (no duplicate positions)

Constraints

• 2 ≤ n ≤ 1000
• 0 ≤ row, col < n
• player is either 1 or 2
• The same cell will not be filled more than once
• At most n² calls will be made to make_move
• Space complexity should be O(n)

Examples

Example 1:

` Board size: 3 Moves: Player 1 -> (0, 0) // Returns 0 Player 2 -> (1, 0) // Returns 0 Player 1 -> (0, 1) // Returns 0 Player 2 -> (1, 1) // Returns 0 Player 1 -> (0, 2) // Returns 1 (completed row 0)

Board state: 1 1 1 2 2 0 0 0 0 `

Example 2:

` Board size: 3 Moves: Player 1 -> (0, 0) // Returns 0 Player 2 -> (0, 1) // Returns 0 Player 1 -> (1, 1) // Returns 0 Player 2 -> (0, 2) // Returns 0 Player 1 -> (2, 2) // Returns 1 (completed main diagonal)

Board state: 1 2 2 0 1 0 0 0 1 `

Example 3:

` Board size: 4 Moves: Player 2 -> (0, 3) // Returns 0 Player 1 -> (1, 0) // Returns 0 Player 2 -> (1, 2) // Returns 0 Player 1 -> (2, 1) // Returns 0 Player 2 -> (2, 1) // Returns 0 Player 1 -> (3, 2) // Returns 0 Player 2 -> (3, 0) // Returns 2 (completed anti-diagonal)

Board state: 0 0 0 2 1 0 2 0 0 2 1 0 2 0 1 0 `