How hard is LeetCode 794. Valid Tic-Tac-Toe State?

LeetCode 794. Valid Tic-Tac-Toe State is rated Medium on LeetCode.

What topics does LeetCode 794. Valid Tic-Tac-Toe State cover?

LeetCode 794. Valid Tic-Tac-Toe State is tagged Array and Matrix on LeetCode.

Valid Tic-Tac-Toe State — LeetCode 794 Python Solution

MediumArrayMatrix

Problem: #794
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

The problem

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'.

Example

Input: board = ["O "," "," "]
Output: false
Explanation: The first player always plays "X".

Python solution

Python

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        def win(x):
            for i in range(3):
                if all(board[i][j] == x for j in range(3)):
                    return True
                if all(board[j][i] == x for j in range(3)):
                    return True
            if all(board[i][i] == x for i in range(3)):
                return True
            return all(board[i][2 - i] == x for i in range(3))

        x = sum(board[i][j] == 'X' for i in range(3) for j in range(3))
        o = sum(board[i][j] == 'O' for i in range(3) for j in range(3))
        if x != o and x - 1 != o:
            return False
        if win('X') and x - 1 != o:
            return False
        return not (win('O') and x != o)

Complexity

Measure	Complexity
Time	O(m·n)
Space	O(1) to O(m·n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 794. Valid Tic-Tac-Toe State is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 794. Valid Tic-Tac-Toe State?: LeetCode 794. Valid Tic-Tac-Toe State is rated Medium on LeetCode.
What topics does LeetCode 794. Valid Tic-Tac-Toe State cover?: LeetCode 794. Valid Tic-Tac-Toe State is tagged Array and Matrix on LeetCode.