Practice/Meta/Leetcode 1275. Find Winner on a Tic Tac Toe Game

Leetcode 1275. Find Winner on a Tic Tac Toe Game

CodingMust

Problem

You are implementing a game state analyzer for a standard 3×3 tic-tac-toe game. Two players take turns placing their marks on the board: Player A goes first with 'X' marks, and Player B follows with 'O' marks.

Given an array of moves where each move is represented as [row, col] indicating the position on the board (0-indexed), determine the current state of the game. The players alternate turns starting with Player A.

Return one of the following strings:

• "A" if Player A has won (three X's in a row horizontally, vertically, or diagonally)
• "B" if Player B has won (three O's in a row horizontally, vertically, or diagonally)
• "Draw" if all 9 positions are filled with no winner
• "Pending" if the game is still in progress

Requirements

1. Process moves in the order they appear in the input array
2. Player A makes the first move (index 0), then players alternate
3. Detect when a player achieves three marks in a row (horizontal, vertical, or diagonal)
4. Distinguish between a completed game with no winner (draw) and an incomplete game (pending)
5. You may assume all moves are valid (no duplicate positions or invalid coordinates)

Constraints

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= row, col <= 2
• All moves are unique and valid positions on the board
• The moves follow the rules of tic-tac-toe (alternating players)
• Time complexity: Aim for O(n) where n is the number of moves
• Space complexity: O(1) additional space is ideal

Examples

Example 1:

Input: moves = [[0,0],[1,0],[0,1],[1,1],[0,2]] Output: "A" Explanation: Player A places marks at (0,0), (0,1), and (0,2), completing the entire top row. Board state: X X X O O . . . .

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0],[2,1],[1,2],[2,2]] Output: "Draw" Explanation: All positions are filled but no player has three in a row. Board state: X O O X X O O X X

Example 3:

Input: moves = [[0,0],[1,0],[0,1]] Output: "Pending" Explanation: Only 3 moves have been made, game continues. Board state: X X . O . . . . .

Example 4:

Input: moves = [[0,0],[0,1],[1,1],[0,2],[2,2]] Output: "A" Explanation: Player A completes the main diagonal with positions (0,0), (1,1), and (2,2). Board state: X O O . X . . . X