Problem Explanation

The problem is to design a game of tic-tac-toe that can be played by two players on a grid of size n x n. In this game, two players take turns to play. Each player has their own symbol ('X' for player 1 and 'O' for player 2). Players take turns placing their symbol on the grid. The first player who manages to place their symbols in a complete vertical, horizontal, or diagonal line wins the game.

The input to the method 'move' will consist a row number, a column number and a player number in order. For each move, if no player has won the game, it returns 0. If player 1 wins it returns 1 and if player 2 wins it returns 2.

The task is to implement this game and method move such that it determines the winner efficiently. An inefficient solution is to check the entire board after each move, which would be an O(n^2) operation. The problem requires to come up with a better solution with time complexity lower than O(n^2).

Explanation of the Solution

We note that for each new move, only the row, column and the diagonals (if any) passing through the current cell get updated and therefore, affect the outcome of the game based on current move. To keep track of these, we maintain counts of 'X's and 'O's for each row, column and diagonals in the game.

Specifically, for each new move in row i and column j by player p, we increment counters for row i, column j and the diagonals if i==j or i+j==n-1, where n is the size of the board. For player 1, we increment the counters, and for player 2, we decrement them. If after the move, any of the counters becomes n or -n, player 1 or player 2 wins, respectively.

In the following, we present solutions based on this approach for different programming languages:

Python Solution

1
2python
3class TicTacToe:
4    
5    def __init__(self, n: int):
6        self.n = n
7        self.rows = [0] * n
8        self.cols = [0] * n
9        self.diag = 0
10        self.anti_diag = 0
11    
12    def move(self, row: int, col: int, player: int) -> int:
13        add = 1 if player == 1 else -1
14        
15        self.rows[row] += add
16        self.cols[col] += add
17        if row == col:
18            self.diag += add
19        if row + col == self.n - 1:
20            self.anti_diag += add
21        
22        if (abs(self.rows[row]) == self.n or 
23            abs(self.cols[col]) == self.n or 
24            abs(self.diag) == self.n or 
25            abs(self.anti_diag) == self.n):
26            return player
27        return 0

Java Solution

1
2java
3public class TicTacToe {
4    private int[][] board;
5    private int[] rows;
6    private int[] cols;
7    private int n, diag, antiDiag;
8    
9    public TicTacToe(int n) {
10        board = new int[n][n];
11        rows = new int[n];
12        cols = new int[n];
13        this.n = n;
14    }
15    
16    public int move(int row, int col, int player) {
17        int value = player == 1 ? 1 : -1;
18        
19        rows[row] += value;
20        cols[col] += value;
21        if (row == col) {
22            diag += value;
23        }
24        if (row + col == n-1) {
25            antiDiag += value;
26        }
27        
28        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
29            Math.abs(diag) == n || Math.abs(antiDiag) == n) {
30            return player;
31        }
32        
33        return 0;
34    }
35}

JavaScript Solution

1
2javascript
3class TicTacToe {
4    constructor(n) {
5        this.rows = new Array(n).fill(0);
6        this.cols = new Array(n).fill(0);
7        this.diag = 0;
8        this.antiDiag = 0;
9        this.n = n;
10    }
11    
12    move(row, col, player) {
13        let add = player === 1 ? 1 : -1;
14        
15        this.rows[row] += add;
16        this.cols[col] += add;
17        if (row === col) {
18            this.diag += add;
19        }
20        if (row + col === this.n - 1) {
21            this.antiDiag += add;
22        }
23        
24        if (Math.abs(this.rows[row]) === this.n || 
25            Math.abs(this.cols[col]) === this.n || 
26            Math.abs(this.diag) === this.n || 
27            Math.abs(this.antiDiag) === this.n) {
28            return player;
29        }
30        
31        return 0;
32    }
33}

C++ Solution

1
2cpp
3class TicTacToe {
4public:
5    TicTacToe(int n) {
6        rows = vector<int>(n, 0);
7        cols = vector<int>(n, 0);
8        diag = 0;
9        antiDiag = 0;
10        this->n = n;
11    }
12    
13    int move(int row, int col, int player) {
14        int add = player == 1 ? 1 : -1;
15        
16        rows[row] += add;
17        cols[col] += add;
18        if (row == col) {
19            diag += add;
20        }
21        if (row + col == n - 1) {
22            antiDiag += add;
23        }
24        
25        if (abs(rows[row]) == n || abs(cols[col]) == n || abs(diag) == n || abs(antiDiag) == n) {
26            return player;
27        }
28        
29        return 0;
30    }
31
32private:
33    vector<int> rows;
34    vector<int> cols;
35    int diag, antiDiag, n;
36};

C# Solution

1
2csharp
3public class TicTacToe {
4    
5    private int[] rows;
6    private int[] cols;
7    private int diag;
8    private int antiDiag;
9    private int n;
10    
11    public TicTacToe(int n) {
12        this.rows = new int[n];
13        this.cols = new int[n];
14        this.n = n;
15    }
16    
17    public int Move(int row, int col, int player) {
18        int add = player == 1 ? 1 : -1;
19        
20        rows[row] += add;
21        cols[col] += add;
22        if (row == col) {
23            diag += add;
24        }
25        if (row + col == n - 1) {
26            antiDiag += add;
27        }
28        
29        if (Math.Abs(rows[row]) == n || Math.Abs(cols[col]) == n || 
30            Math.Abs(diag) == n || Math.Abs(antiDiag) == n) {
31            return player;
32        }
33        
34        return 0;
35    }
36}

As you can see, the implementation in every language follows the same logic as explained above.# Key Takeaways

What makes this solution efficient is that it checks only the relevant parts of the board after each move instead of checking the entire board. It maintains counters for each row, column, and diagonals, and increment the counters whenever a move is made. It avoids unnecessary repetition and reduces the time complexity significantly.

The solution adopts a "count as you go" approach, keeping track of the game's progression, which is much more time and space efficient than checking the entire grid repeatedly. This is an example of how we can use simple tools, such as arrays, to track certain criteria in the problem, drastically reducing time complexity.

This problem teaches the following concepts:

• How to maintain and update information dynamically to avoid repeated computations.
• How adding counters can significantly bring down time complexity.
• The importance of identifying and optimizing the parts of a problem that need to be checked repeatedly.

The suggested solutions, although presented for a game of tic-tac-toe, can also be useful in other similar problems where we have to keep track of the changes happening in real time. This method of computation can be expanded to accommodate larger grids, other games or more complex settings.

While these implementations take into account valid moves only, they can be expanded to include checks for invalid moves as well. Always remember, a key part to solving large programming problems is breaking them down into smaller parts and tackling those. In this case, breaking the grid down and monitoring them individually proved to be the effective solution.