Valid Tic-Tac-Toe State solution and explanation
8 more videos on this problem
Valid Tic-Tac-Toe State | Top Google Coding Interview QuestionCoding Courses · 9:23 · 1K views
【每日一题】794 Valid Tic-Tac-Toe State, 04/16/2019Huifeng Guan · 10:36 · 1K views
794. Valid Tic-Tac-Toe State (Leetcode Medium)Programming Live with Larry · 8:59 · 578 views
Leetcode 794. Valid Tic-Tac-Toe State (design step by step)LetsCode · 13:29 · 283 views
794. Valid Tic-Tac-Toe StateJust Coding, with Jie · 19:25 · 160 views
[Readable LeetCode Solution] Valid Tic-Tac-Toe State: Simplified Solution & In-Depth ExplanationFrontend Infra · 13:43 · 105 views
LeetCode 794 JavaHow we live in Texas · 5:27 · 65 views
No Sound Leetcode 794: Valid Tic-Tac-Toe StateExtremeProgrammer · 6:11 · 39 views
LeetCode 794: Valid Tic-Tac-Toe StateAlitaCode · 27:42 · 32 views
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'. The ' ' character represents an empty square.
Here are the 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.
Example 1:
Input: board = ["O "," "," "] Output: false Explanation: The first player always plays "X".
Example 2:
Input: board = ["XOX"," X "," "] Output: false Explanation: Players take turns making moves.
Example 3:
Input: board = ["XOX","O O","XOX"] Output: true
Constraints:
board.length == 3board[i].length == 3board[i][j]is either'X','O', or' '.
Approach overview
Problem Overview: You receive a 3x3 Tic-Tac-Toe board represented as strings. The board may contain 'X', 'O', or empty cells. The task is to verify whether this board state could occur during a real game where players alternate turns and follow standard Tic-Tac-Toe rules.
The tricky part is not checking wins but validating whether the sequence of moves that produced the board is legal. Since players alternate turns and 'X' always starts first, the counts of moves and the presence of winning lines must follow strict rules.
Approach 1: Count and Validate Turns (O(1) time, O(1) space)
Iterate through the 3x3 board and count how many times 'X' and 'O' appear. In a valid game, X_count must either equal O_count or exceed it by exactly one because 'X' always plays first. After counting, scan the board for winning combinations across rows, columns, and diagonals.
If 'X' wins, there must be exactly one more 'X' move than 'O'. If 'O' wins, both players must have the same number of moves. Any board where both players win simultaneously is invalid. This approach works by directly enforcing the logical constraints of the game rather than simulating moves. The board size is fixed, so scanning rows, columns, and diagonals takes constant time.
This approach primarily operates on the board grid itself, making it a straightforward use of array traversal and matrix pattern checking.
Approach 2: Mathematical Logical Check (O(1) time, O(1) space)
Instead of treating validation as multiple independent checks, you can encode the rules as mathematical conditions. First compute the counts of 'X' and 'O'. Then compute two boolean flags: whether 'X' has a winning line and whether 'O' has a winning line. Each flag is determined by checking the 8 possible win patterns.
Once you have these values, apply logical constraints: the difference between move counts must be valid, both players cannot win simultaneously, and the winning player must match the move order rules. For example, if xWin is true but X_count == O_count, the state is impossible because 'X' must have just played.
This approach condenses the entire validation into a small set of boolean conditions. It is often preferred when you want a clean and interview-friendly implementation with minimal branching.
Recommended for interviews: The count-and-validate approach is what most interviewers expect. It shows that you understand the game constraints and can systematically check rows, columns, and diagonals. The mathematical logical check is slightly cleaner once you recognize the constraints, but both run in constant time and space due to the fixed 3x3 board.
Approach 1: Approach 1: Count and Validate Turns
This approach involves counting the number of 'X' and 'O' on the board and validating a tic-tac-toe board based on the count and winning conditions.
1. Count the number of 'X' and 'O'.
2. Ensure that the number of 'O's is not greater than the number of 'X's and that the number of 'X's does not exceed the number of 'O's by more than one.
3. Check win states for 'X' and 'O'.
4. If both players have a winning line, the board is invalid.
The goal is to ensure the board could have been created by valid game play.
class Solution:
def win(self, player, board):
for i in range(3):
if board[i][0] == player and board[i][1] == player and board[i][2] == player:
return True
if board[0][i] == player and board[1][i] == player and board[2][i] == player:
return True
if board[0][0] == player and board[1][1] == player and board[2][2] == player:
return True
if board[0][2] == player and board[1][1] == player and board[2][0] == player:
return True
return False
def isValidTicTacToe(self, board):
xCount = oCount = 0
for row in board:
xCount += row.count('X')
oCount += row.count('O')
if oCount > xCount or xCount > oCount + 1:
return False
if self.win('X', board) and xCount != oCount + 1:
return False
if self.win('O', board) and xCount != oCount:
return False
return Trueclass Solution {
public boolean win(char player, char[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
public boolean isValidTicTacToe(char[][] board) {
int xCount = 0, oCount = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 'X') xCount++;
if (board[i][j] == 'O') oCount++;
}
}
if (oCount > xCount || xCount > oCount + 1) return false;
if (win('X', board) && xCount != oCount + 1) return false;
if (win('O', board) && xCount != oCount) return false;
return true;
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool win(char player, vector<string>& board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == board[2][0]) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
bool isValidTicTacToe(vector<string>& board) {
int xCount = 0, oCount = 0;
for (const auto& row : board) {
for (char c : row) {
if (c == 'X') xCount++;
if (c == 'O') oCount++;
}
}
if (oCount > xCount || xCount > oCount + 1) return false;
if (win('X', board) && xCount != oCount + 1) return false;
if (win('O', board) && xCount != oCount) return false;
return true;
}
};var isValidTicTacToe = function(board) {
const win = (player) => {
for (let i = 0; i < 3; i++) {
if (board[i][0] === player && board[i][1] === player && board[i][2] === player) return true;
if (board[0][i] === player && board[1][i] === player && board[2][i] === player) return true;
}
if (board[0][0] === player && board[1][1] === player && board[2][2] === player) return true;
if (board[0][2] === player && board[1][1] === player && board[2][0] === player) return true;
return false;
};
let xCount = 0, oCount = 0;
for (let row of board) {
for (let c of row) {
if (c === 'X') xCount++;
if (c === 'O') oCount++;
}
}
if (oCount > xCount || xCount > oCount + 1) return false;
if (win('X') && xCount !== oCount + 1) return false;
if (win('O') && xCount !== oCount) return false;
return true;
};#include <stdbool.h>
bool win(char player, char board[3][3]) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
bool isValid(char board[3][3]) {
int xCount = 0, oCount = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 'X') xCount++;
if (board[i][j] == 'O') oCount++;
}
}
if (oCount > xCount || xCount > oCount + 1) return false;
if (win('X', board) && xCount != oCount + 1) return false;
if (win('O', board) && xCount != oCount) return false;
return true;
}public class Solution {
public bool Win(char player, char[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
public bool IsValidTicTacToe(char[][] board) {
int xCount = 0, oCount = 0;
foreach (var row in board) {
foreach (var c in row) {
if (c == 'X') xCount++;
if (c == 'O') oCount++;
}
}
if (oCount > xCount || xCount > oCount + 1) return false;
if (Win('X', board) && xCount != oCount + 1) return false;
if (Win('O', board) && xCount != oCount) return false;
return true;
}
}In this Python solution, we check for win states and compare the counts of 'X's and 'O's using Python's list operations and count method.
Time Complexity: O(1) - We process a fixed 3x3 board.
Space Complexity: O(1) - No additional space is required.
Approach 2: Approach 2: Mathematical Logical Check
In this approach, we don't just account for the counts but also utilize a logical check to directly evaluate win conditions and ensure the configuration aligns with tic-tac-toe game rules.
1. Assess characters' count to validate play sequence.
2. Use mathematical logic to quickly determine if any win condition is met by checking all board positions.
3. Ensure there's no possibility of two winners in the current game state.
The aim is to provide a quick validity response based on the typical outcomes of a tic-tac-toe game.
class Solution:
def count(self, player, board):
return sum(row.count(player) for row in board)
def checkWin(self, player, board):
for i in range(3):
if board[i][0] == player and board[i][1] == player and board[i][2] == player:
return True
if board[0][i] == player and board[1][i] == player and board[2][i] == player:
return True
if board[0][0] == player and board[1][1] == player and board[2][2] == player:
return True
if board[0][2] == player and board[1][1] == player and board[2][0] == player:
return True
return False
def isValidTicTacToe(self, board):
xCount = self.count('X', board)
oCount = self.count('O', board)
if oCount > xCount or xCount > oCount + 1:
return False
if self.checkWin('X', board) and xCount != oCount + 1:
return False
if self.checkWin('O', board) and xCount != oCount:
return False
return Trueclass Solution {
public int count(char player, char[][] board) {
int count = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == player) count++;
}
}
return count;
}
public boolean checkWin(char player, char[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
public boolean isValidTicTacToe(char[][] board) {
int xCount = count('X', board);
int oCount = count('O', board);
if (oCount > xCount || xCount > oCount + 1) return false;
if (checkWin('X', board) && xCount != oCount + 1) return false;
if (checkWin('O', board) && xCount != oCount) return false;
return true;
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int count(char player, vector<string>& board) {
int count = 0;
for (const auto& row : board) {
for (const auto& cell : row) {
if (cell == player) count++;
}
}
return count;
}
bool checkWin(char player, vector<string>& board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
bool isValidTicTacToe(vector<string>& board) {
int xCount = count('X', board);
int oCount = count('O', board);
if (oCount > xCount || xCount > oCount + 1) return false;
if (checkWin('X', board) && xCount != oCount + 1) return false;
if (checkWin('O', board) && xCount != oCount) return false;
return true;
}
};var isValidTicTacToe = function(board) {
const count = (player) => {
let count = 0;
for (let row of board) {
for (let char of row) {
if (char === player) count++;
}
}
return count;
};
const checkWin = (player) => {
for (let i = 0; i < 3; i++) {
if (board[i][0] === player && board[i][1] === player && board[i][2] === player) return true;
if (board[0][i] === player && board[1][i] === player && board[2][i] === player) return true;
}
if (board[0][0] === player && board[1][1] === player && board[2][2] === player) return true;
if (board[0][2] === player && board[1][1] === player && board[2][0] === player) return true;
return false;
};
let xCount = count('X');
let oCount = count('O');
if (oCount > xCount || xCount > oCount + 1) return false;
if (checkWin('X') && xCount !== oCount + 1) return false;
if (checkWin('O') && xCount !== oCount) return false;
return true;
};#include <stdbool.h>
int count(char player, char board[3][3]) {
int count = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == player) count++;
}
}
return count;
}
bool checkWin(char player, char board[3][3]) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
bool isValid(char board[3][3]) {
int xCount = count('X', board);
int oCount = count('O', board);
if (oCount > xCount || xCount > oCount + 1) return false;
if (checkWin('X', board) && xCount != oCount + 1) return false;
if (checkWin('O', board) && xCount != oCount) return false;
return true;
}public class Solution {
public int Count(char player, char[][] board) {
int count = 0;
foreach (var row in board) {
foreach (var c in row) {
if (c == player) count++;
}
}
return count;
}
public bool CheckWin(char player, char[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
return false;
}
public bool IsValidTicTacToe(char[][] board) {
int xCount = Count('X', board);
int oCount = Count('O', board);
if (oCount > xCount || xCount > oCount + 1) return false;
if (CheckWin('X', board) && xCount != oCount + 1) return false;
if (CheckWin('O', board) && xCount != oCount) return false;
return true;
}
}The Python solution uniquely measures character logistics while executing simultaneously winning validation in alignment with board integrity.
Time Complexity: O(1) - Characteristic logical checks against definitive benchmarks.
Space Complexity: O(1) - Capacity bound by logical processing frame.
Approach 3: Default Approach
func validTicTacToe(board []string) bool {
var x, o int
for _, row := range board {
for _, c := range row {
if c == 'X' {
x++
} else if c == 'O' {
o++
}
}
}
win := func(x byte) bool {
for i := 0; i < 3; i++ {
if board[i][0] == x && board[i][1] == x && board[i][2] == x {
return true
}
if board[0][i] == x && board[1][i] == x && board[2][i] == x {
return true
}
}
if board[0][0] == x && board[1][1] == x && board[2][2] == x {
return true
}
return board[0][2] == x && board[1][1] == x && board[2][0] == x
}
if x != o && x-1 != o {
return false
}
if win('X') && x-1 != o {
return false
}
return !(win('O') && x != o)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Count and Validate Turns | Time Complexity: O(1) - We process a fixed 3x3 board. |
| Approach 2: Mathematical Logical Check | Time Complexity: O(1) - Characteristic logical checks against definitive benchmarks. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count and Validate Turns | O(1) | O(1) | Best general approach. Easy to reason about and clearly follows Tic-Tac-Toe rules. |
| Mathematical Logical Check | O(1) | O(1) | When you want a concise implementation using logical constraints instead of step-by-step validation. |
Frequently asked questions
Is Valid Tic-Tac-Toe State easy or hard?
Valid Tic-Tac-Toe State is typically classified as a Medium problem. The board traversal is simple, but the challenge lies in correctly enforcing all game constraints and handling edge cases such as simultaneous wins or invalid move counts.
Valid Tic-Tac-Toe State Python/Java solution
Most implementations follow the same pattern: count 'X' and 'O', write a helper function to check whether a player has a winning line, then validate the counts against the winner conditions. The logic translates directly across Python, Java, C++, JavaScript, and C#.
How to solve Valid Tic-Tac-Toe State in O(1)?
Scan the 3x3 board once to count 'X' and 'O'. Then check all rows, columns, and diagonals to detect if either player has a winning line. Apply logical constraints: X must have either the same number of moves as O or exactly one more, both players cannot win simultaneously, and the winner must match the move count rule.
What is the best approach for Valid Tic-Tac-Toe State?
The count-and-validate approach is the most reliable solution. Count how many 'X' and 'O' moves exist, then verify winning lines across rows, columns, and diagonals. Apply the game rules: 'X' starts first, move counts must differ by at most one, and the winning player must match the move order. This method runs in O(1) time because the board size is fixed.
Is Valid Tic-Tac-Toe State asked at Google/Amazon/Meta?
Variants of board validation and game-state checking problems appear in interviews at companies like Google, Amazon, and Meta. The problem tests logical reasoning, matrix traversal, and edge-case handling rather than heavy algorithmic complexity.
What data structure is used in Valid Tic-Tac-Toe State?
The primary data structure is a 2D board represented as a matrix or array of strings. The solution iterates through the matrix to count symbols and evaluate row, column, and diagonal win patterns.
What is the time complexity of Valid Tic-Tac-Toe State?
The time complexity is O(1). The board is always a fixed 3x3 grid, so counting symbols and checking the 8 possible winning lines takes constant time regardless of input. Space complexity is also O(1) since only a few counters and boolean flags are used.