Skip to content

348. Design Tic-Tac-Toe 👍

  • Time: $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class TicTacToe {
 public:
  TicTacToe(int n) : n(n), rows(n), cols(n) {}

  /**
   * Player {player} makes a move at ({row}, {col}).
   *
   * @param row    The row of the board.
   * @param col    The column of the board.
   * @param player The player, can be either 1 or 2.
   * @return The current winning condition, can be either:
   *         0: No one wins.
   *         1: Player 1 wins.
   *         2: Player 2 wins.
   */
  int std::move(int row, int col, int player) {
    const int toAdd = player == 1 ? 1 : -1;
    const int target = player == 1 ? n : -n;

    if (row == col) {
      diag += toAdd;
      if (diag == target)
        return player;
    }

    if (row + col == n - 1) {
      antiDiag += toAdd;
      if (antiDiag == target)
        return player;
    }

    rows[row] += toAdd;
    if (rows[row] == target)
      return player;

    cols[col] += toAdd;
    if (cols[col] == target)
      return player;

    return 0;
  }

 private:
  const int n;
  // Record count('X') - count('O').
  vector<int> rows;
  vector<int> cols;
  int diag = 0;
  int antiDiag = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class TicTacToe {
  public TicTacToe(int n) {
    this.n = n;
    rows = new int[n];
    cols = new int[n];
  }

  /**
   * Player {player} makes a move at ({row}, {col}).
   *
   * @param row    The row of the board.
   * @param col    The column of the board.
   * @param player The player, can be either 1 or 2.
   * @return The current winning condition, can be either:
   *         0: No one wins.
   *         1: Player 1 wins.
   *         2: Player 2 wins.
   */
  public int move(int row, int col, int player) {
    final int toAdd = player == 1 ? 1 : -1;
    final int target = player == 1 ? n : -n;

    if (row == col) {
      diag += toAdd;
      if (diag == target)
        return player;
    }

    if (row + col == n - 1) {
      antiDiag += toAdd;
      if (antiDiag == target)
        return player;
    }

    rows[row] += toAdd;
    if (rows[row] == target)
      return player;

    cols[col] += toAdd;
    if (cols[col] == target)
      return player;

    return 0;
  }

  private final int n;
  // Record count('X') - count('O').
  private int[] rows;
  private int[] cols;
  private int diag = 0;
  private int antiDiag = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class TicTacToe:
  def __init__(self, n: int):
    self.n = n
    # Record count('X') - count('O').
    self.rows = [0] * n
    self.cols = [0] * n
    self.diag = 0
    self.antiDiag = 0

  """ Player {player} makes a move at ({row}, {col}).

      @param row    The row of the board.
      @param col    The column of the board.
      @param player The player, can be either 1 or 2.
      @return The current winning condition, can be either:
              0: No one wins.
              1: Player 1 wins.
              2: Player 2 wins.
  """

  def move(self, row: int, col: int, player: int) -> int:
    toAdd = 1 if player == 1 else -1
    target = self.n if player == 1 else -self.n

    if row == col:
      self.diag += toAdd
      if self.diag == target:
        return player

    if row + col == self.n - 1:
      self.antiDiag += toAdd
      if self.antiDiag == target:
        return player

    self.rows[row] += toAdd
    if self.rows[row] == target:
      return player

    self.cols[col] += toAdd
    if self.cols[col] == target:
      return player

    return 0