FastPrepFastPrep
Problem Brief

Tic-Tac-Toe Game Status

FULLTIMENEW GRADPHONE SCREEN
See Google online assessment and hiring insights

Design the move-processing logic for a generalized Tic-Tac-Toe game.

There are k players and an n x n board. Players take turns placing their own mark on an empty cell. Player numbers are 1 through k.

A player wins as soon as they have at least 3 consecutive marks in a straight line. The line may be horizontal, vertical, diagonal, or anti-diagonal. This winning length is always 3, even when n is larger than 3.

Given the move list, return the game status after each move:

  • "Game Over" if the move is attempted after a winner already exists.
  • "Player X won" if player X wins on that move.
  • "Draw" if the board becomes full and nobody has won.
  • "In Progress" otherwise.

All moves in the input are within board bounds. If a move targets an already occupied cell before the game is over, leave the board unchanged and return "Invalid Move" for that move.

1Example 1

Input
k = 2, n = 3, moves = [[1,0,0],[2,1,0],[1,0,1],[2,1,1],[1,0,2]]
Output
["In Progress","In Progress","In Progress","In Progress","Player 1 won"]
Explanation

Player 1 completes three consecutive marks across the top row.

2Example 2

Input
k = 3, n = 4, moves = [[1,0,0],[2,0,1],[3,3,3],[1,1,1],[2,1,0],[3,2,1],[1,2,2]]
Output
["In Progress","In Progress","In Progress","In Progress","In Progress","In Progress","Player 1 won"]
Explanation

Player 1 completes the diagonal segment (0,0), (1,1), (2,2).

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= k <= 10
  • 3 <= n <= 10^3
  • 1 <= moves.length <= min(n^2 + 5, 10^5)
  • Each move is encoded as [player, row, col], where 1 <= player <= k and 0 <= row, col < n.
public String[] getGameStatus(int k, int n, int[][] moves) {
    // write your code here
}
Input

k

2

n

3

moves

[[1,0,0],[2,1,0],[1,0,1],[2,1,1],[1,0,2]]

Output

["In Progress", "In Progress", "In Progress", "In Progress", "Player 1 won"]

Sign in to submit your solution.