Valid Tic-Tac-Toe State - Practice Coding Problems

Valid Tic-Tac-Toe State - Problem

Array Matrix Medium

Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array that consists of characters ' ', 'X', and 'O'. The ' ' character represents an empty square.

Rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares ' '
The first player always places 'X' characters, while the second player always places 'O' characters
'X' and 'O' characters are always placed into empty squares, never 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

Input & Output

Example 1 — Valid Game State

$ Input: board = ["O ", " ", " "]

› Output: false

💡 Note: O went first, but X should always go first. This violates the turn order rule.

Example 2 — Valid Game State

$ Input: board = ["XOX", " X ", " "]

› Output: false

💡 Note: X has 3 moves and O has 1 move. Since X goes first, this means O should have made 2 moves. Invalid turn count.

Example 3 — Valid End State

$ Input: board = ["XXX", " ", "OOO"]

› Output: false

💡 Note: Both X and O have winning lines, which is impossible in a valid game. Only one player can win.

Constraints

board.length == 3
board[i].length == 3
board[i][j] is either 'X', 'O', or ' '

Visualization

Tap to expand

Understanding the Visualization

Input Board

3x3 tic-tac-toe board with X, O, and empty spaces

Rule Validation

Check turn order, win conditions, and game state rules

Valid/Invalid

Return true if board state is reachable, false otherwise

Key Takeaway

🎯 Key Insight: Valid tic-tac-toe states must follow turn order (X first) and game-ending rules

Asked in

G Google 15 a Amazon 12 M Microsoft 10 A Apple 8

The key insight is that X always goes first in tic-tac-toe, so valid states must follow strict turn ordering and winning rules. Best approach validates all rules systematically: count pieces, check turn order, detect winners, and ensure game stops after victory. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single-Pass Validation	O(1)	O(1)	Validate all rules in a single pass through the board with optimized checks
Rule-by-Rule Validation	O(1)	O(1)	Check each tic-tac-toe rule individually to validate the board state

Single-Pass Validation — Algorithm Steps

Single pass: count pieces and detect wins simultaneously
Apply all validation rules
Return result based on combined checks

Visualization

Tap to expand

Step-by-Step Walkthrough

Count & Check

Count pieces and validate turn order in one pass

Win Detection

Check all win conditions efficiently

Final Validation

Apply winner rules and return result

Code -

solution.c — C

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

bool checkWinner(char board[3][4], char player) {
    // Combined row and column check
    for (int i = 0; i < 3; i++) {
        bool rowWin = true, colWin = true;
        for (int j = 0; j < 3; j++) {
            if (board[i][j] != player) rowWin = false;
            if (board[j][i] != player) colWin = false;
        }
        if (rowWin || colWin) return true;
    }
    
    // Diagonals
    return (board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
           (board[0][2] == player && board[1][1] == player && board[2][0] == player);
}

bool solution(char board[3][4]) {
    int xCount = 0, oCount = 0;
    
    // Efficient counting
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 'X') xCount++;
            else if (board[i][j] == 'O') oCount++;
        }
    }
    
    // Early exit
    if (!(xCount == oCount || xCount == oCount + 1)) return false;
    
    bool xWins = checkWinner(board, 'X');
    bool oWins = checkWinner(board, 'O');
    
    // Combined validation
    return !(xWins && oWins) && 
           !(xWins && xCount != oCount + 1) && 
           !(oWins && xCount != oCount);
}

int main() {
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    char board[3][4];
    char *start = strchr(line, '[');
    char *token = strtok(start + 1, ",");
    
    for (int i = 0; i < 3; i++) {
        while (*token == ' ' || *token == '"') token++;
        char *end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) end--;
        *(end + 1) = '\0';
        
        strcpy(board[i], token);
        board[i][3] = '\0';
        
        if (i < 2) token = strtok(NULL, ",");
    }
    
    printf(solution(board) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed 3x3 board, constant operations regardless of input

✓ Linear Growth

Space Complexity

O(1)

Only using fixed variables, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Single-Pass Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler