Valid Tic-Tac-Toe State

Medium
1564.

Valid Tic-Tac-Toe State

Valid Tic-Tac-Toe State is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Microsoft and Meta interviews.

A tic-tac-toe board is given as 3 strings of 3 characters, each 'X', 'O' or ' ' (an empty square).

Two players take turns placing marks on empty squares: the first player always places 'X', the second always 'O'. The game ends as soon as one player has three of their marks in a row, column or diagonal, or when all nine squares are filled; no marks are placed after that.

Return true if this board can appear at some point during a valid game, and false otherwise.

Example 1

Input
board = ["O "," "," "]
Output
false
Explanation
`'X'` always moves first, so a lone `'O'` is impossible.

Example 2

Input
board = ["XXX","OO "," "]
Output
true
Explanation
X completes the top row on its third move, after O's second move.

Example 3

Input
board = ["XXX"," ","OOO"]
Output
false
Explanation
Both players cannot have won — the game would have ended at the first win.

Constraints

  • board.length == 3
  • board[i].length == 3
  • board[i][j] is 'X', 'O' or ' '
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} board
 * @return {boolean}
 */
var validTicTacToe = function(board) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Tic-Tac-Toe State — Solution in Python, Java & C++

Valid Tic-Tac-Toe State solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Valid Tic-Tac-Toe State is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon, Microsoft, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A tic-tac-toe board is given as 3 strings of 3 characters, each 'X', 'O' or ' ' (an empty square).

Two players take turns placing marks on empty squares: the first player always places 'X', the second always 'O'. The game ends as soon as one player has three of their marks in a row, column or diagonal, or when all nine squares are filled; no marks are placed after that.

Return true if this board can appear at some point during a valid game, and false otherwise.

Example 1

Input: board = ["O  ","   ","   "]
Output: false
Explanation: `'X'` always moves first, so a lone `'O'` is impossible.

Example 2

Input: board = ["XXX","OO ","   "]
Output: true
Explanation: X completes the top row on its third move, after O's second move.

Example 3

Input: board = ["XXX","   ","OOO"]
Output: false
Explanation: Both players cannot have won — the game would have ended at the first win.

Constraints

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

Hints for Valid Tic-Tac-Toe State

  1. Hint 1

    Count the marks. Since X moves first and players alternate, how must the counts relate?

  2. Hint 2

    If X has three in a row, the game ended right after one of X's moves. What does that say about the counts?

  3. Hint 3

    Valid exactly when: x == o or x == o + 1; if X has a line then x == o + 1; if O has a line then x == o.

How to solve Valid Tic-Tac-Toe State

A board is reachable exactly when its mark counts fit the turn order and any completed line belongs to the player who moved last.

Approach

  1. Count x and o. If not (x == o or x == o + 1), return false.
  2. Check whether X has three in a line and whether O does.
  3. If X has a line and x != o + 1, return false — X's winning move must have been the last.
  4. If O has a line and x != o, return false — O's winning move must have been the last.
  5. Otherwise return true.

Why it works

The conditions are necessary: turns alternate starting with X, and play stops right after a winning move, so the winner must have moved last. They are also sufficient: given counts that fit, remove the marks in an order that keeps a winning line's last mark until the very end — every earlier position then contains no completed line, so the game could have reached this board. (Both players winning is ruled out automatically, since it would need x == o + 1 and x == o at once.)

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • X may legitimately have two winning lines at once (one move completing both), so do not reject a double line.
  • A full board with no winner is valid if x == 5 and o == 4.
  • Spaces are significant characters in the rows — do not trim them.

Reference solution

Python

from typing import List

def validTicTacToe(board: List[str]) -> bool:
    x = sum(row.count('X') for row in board)
    o = sum(row.count('O') for row in board)
    if o > x or x > o + 1:
        return False

    def wins(p):
        for k in range(3):
            if all(board[k][j] == p for j in range(3)):
                return True
            if all(board[i][k] == p for i in range(3)):
                return True
        if all(board[i][i] == p for i in range(3)):
            return True
        return all(board[i][2 - i] == p for i in range(3))

    if wins('X') and x != o + 1:
        return False
    if wins('O') and x != o:
        return False
    return True

Java

public static boolean validTicTacToe(String[] board) {
    int x = 0, o = 0;
    for (String row : board) for (char ch : row.toCharArray()) {
        if (ch == 'X') x++;
        else if (ch == 'O') o++;
    }
    if (o > x || x > o + 1) return false;
    if (winsTtt(board, 'X') && x != o + 1) return false;
    if (winsTtt(board, 'O') && x != o) return false;
    return true;
}

private static boolean winsTtt(String[] b, char p) {
    for (int k = 0; k < 3; k++) {
        if (b[k].charAt(0) == p && b[k].charAt(1) == p && b[k].charAt(2) == p) return true;
        if (b[0].charAt(k) == p && b[1].charAt(k) == p && b[2].charAt(k) == p) return true;
    }
    return (b[0].charAt(0) == p && b[1].charAt(1) == p && b[2].charAt(2) == p)
        || (b[0].charAt(2) == p && b[1].charAt(1) == p && b[2].charAt(0) == p);
}

C++

static bool winsTtt(vector<string>& b, char p) {
    for (int k = 0; k < 3; k++) {
        if (b[k][0] == p && b[k][1] == p && b[k][2] == p) return true;
        if (b[0][k] == p && b[1][k] == p && b[2][k] == p) return true;
    }
    return (b[0][0] == p && b[1][1] == p && b[2][2] == p) || (b[0][2] == p && b[1][1] == p && b[2][0] == p);
}

bool validTicTacToe(vector<string>& board) {
    int x = 0, o = 0;
    for (auto& row : board) for (char ch : row) {
        if (ch == 'X') x++;
        else if (ch == 'O') o++;
    }
    if (o > x || x > o + 1) return false;
    if (winsTtt(board, 'X') && x != o + 1) return false;
    if (winsTtt(board, 'O') && x != o) return false;
    return true;
}

JavaScript

var validTicTacToe = function(board) {
    var x = 0, o = 0;
    for (var i = 0; i < 3; i++) for (var j = 0; j < 3; j++) {
        if (board[i][j] === 'X') x++;
        else if (board[i][j] === 'O') o++;
    }
    if (o > x || x > o + 1) return false;
    var wins = function(p) {
        for (var k = 0; k < 3; k++) {
            if (board[k][0] === p && board[k][1] === p && board[k][2] === p) return true;
            if (board[0][k] === p && board[1][k] === p && board[2][k] === p) return true;
        }
        return (board[0][0] === p && board[1][1] === p && board[2][2] === p) ||
            (board[0][2] === p && board[1][1] === p && board[2][0] === p);
    };
    if (wins('X') && x !== o + 1) return false;
    if (wins('O') && x !== o) return false;
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal