Find Winner on a Tic Tac Toe Game - Practice Coding Problems

Find Winner on a Tic Tac Toe Game - Problem

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

Players take turns placing characters into empty squares ' '
The first player A always places 'X' characters, while the second player B always places 'O' characters
'X' and 'O' characters are always placed into empty squares, never on filled ones
The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal
The game also ends if all squares are non-empty
No more moves can be played if the game is over

Given a 2D integer array moves where moves[i] = [row_i, col_i] indicates that the i^th move will be played on grid[row_i][col_i].

Return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Input & Output

Example 1 — Player A Wins

$ Input: moves = [[0,0],[2,0],[1,1],[1,0],[2,1]]

› Output: A

💡 Note: Player A (X) places at positions creating column: (0,0), (1,1), (2,1). After move 5, A has three X's in column 1, so A wins.

Example 2 — Draw Game

$ Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0],[1,2],[2,1],[2,2]]

› Output: Draw

💡 Note: All 9 squares are filled with no three in a row. The game ends in a draw.

Example 3 — Game Pending

$ Input: moves = [[0,0],[1,1],[2,0]]

› Output: Pending

💡 Note: Only 3 moves played, no winner yet, and the board is not full. Game is still pending.

Constraints

1 ≤ moves.length ≤ 9
moves[i].length == 2
0 ≤ row_i, col_i ≤ 2
There are no repeated moves.
moves follow the rules of tic tac toe.

Visualization

Tap to expand

Understanding the Visualization

Input Moves

Array of [row,col] positions in order

Simulate Game

Place X and O alternately, check for wins

Determine Result

A wins, B wins, Draw, or Pending

Key Takeaway

🎯 Key Insight: Only check for wins after each move, and use efficient counting to avoid building the full board

Asked in

A Amazon 15 M Microsoft 8

The key insight is to track winning conditions efficiently without building the full board. Use counters for each row, column, and diagonal: Player A adds +1, Player B adds -1. A win occurs when any counter reaches ±3. Best approach is count-based tracking with Time: O(m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Count-Based Tracking	O(m)	O(1)	Track sums for each row, column, and diagonal to detect wins without building full board
Simulate Full Board	O(m)	O(1)	Build the complete 3x3 board and check all winning conditions after each move

Count-Based Tracking — Algorithm Steps

Initialize counters for 3 rows, 3 columns, 2 diagonals
For each move, update relevant counters (+1 for A, -1 for B)
Check if any counter reaches ±3 (winner found)
Return appropriate result based on game state

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Counters

Set up arrays for rows, cols, diagonals

Update Counters

Add +1 for A, -1 for B to relevant lines

Check Win

Look for ±3 in any counter

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

char* solution(int moves[][2], int movesSize) {
    // Track counts for rows, cols, diagonals
    int rows[3] = {0, 0, 0};
    int cols[3] = {0, 0, 0};
    int diag1 = 0;  // main diagonal (0,0) to (2,2)
    int diag2 = 0;  // anti diagonal (0,2) to (2,0)
    
    for (int i = 0; i < movesSize; i++) {
        int row = moves[i][0];
        int col = moves[i][1];
        // Player A gets +1, Player B gets -1
        int playerVal = i % 2 == 0 ? 1 : -1;
        
        // Update counters
        rows[row] += playerVal;
        cols[col] += playerVal;
        if (row == col) {
            diag1 += playerVal;
        }
        if (row + col == 2) {
            diag2 += playerVal;
        }
        
        // Check for winner
        if (abs_val(rows[row]) == 3 || abs_val(cols[col]) == 3 || 
            abs_val(diag1) == 3 || abs_val(diag2) == 3) {
            char* result = malloc(2);
            strcpy(result, playerVal == 1 ? "A" : "B");
            return result;
        }
    }
    
    // No winner yet
    char* result = malloc(8);
    strcpy(result, movesSize == 9 ? "Draw" : "Pending");
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[r,c],[r,c],...]
    int moves[9][2];
    int movesSize = 0;
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            moves[movesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            moves[movesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            movesSize++;
        }
        ptr++;
    }
    
    char* result = solution(moves, movesSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m)

Process each of m moves once, updating counters in constant time

✓ Linear Growth

Space Complexity

O(1)

Uses fixed arrays for 3 rows + 3 cols + 2 diagonals = 8 integers total

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Count-Based Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler