#794
Medium Algorithms Valid tic tac toe state
Array Matrix
34.8% acceptance
Feb 21, 2026
587
1168
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.
Solution
Rust
Time O(n)
Space O(1)
/*
* 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 == 3
* board[i].length == 3
* board[i][j] is either 'X', 'O', or ' '.
*/
impl Solution {
pub fn valid_tic_tac_toe(board: Vec<String>) -> bool {
let b: Vec<Vec<char>> = board.iter().map(|s| s.chars().collect()).collect();
let count_x = b.iter().flatten().filter(|&&c| c == 'X').count() as i32;
let count_o = b.iter().flatten().filter(|&&c| c == 'O').count() as i32;
if count_x != count_o && count_x != count_o + 1 { return false; }
let wins = |p: char| -> bool {
for i in 0..3 {
if b[i].iter().all(|&c| c == p) { return true; }
if (0..3).all(|j| b[j][i] == p) { return true; }
}
if (0..3).all(|i| b[i][i] == p) { return true; }
if (0..3).all(|i| b[i][2-i] == p) { return true; }
false
};
let x_wins = wins('X');
let o_wins = wins('O');
if x_wins && o_wins { return false; }
if x_wins && count_x != count_o + 1 { return false; }
if o_wins && count_x != count_o { return false; }
true
}
}