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 == 3board[i].length == 3board[i][j] is 'X', 'O' or ' '
Hints for Valid Tic-Tac-Toe State
Hint 1
Count the marks. Since X moves first and players alternate, how must the counts relate?
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?
Hint 3
Valid exactly when:
x == oorx == o + 1; if X has a line thenx == o + 1; if O has a line thenx == 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
- Count
xando. If not (x == oorx == o + 1), returnfalse. - Check whether X has three in a line and whether O does.
- If X has a line and
x != o + 1, returnfalse— X's winning move must have been the last. - If O has a line and
x != o, returnfalse— O's winning move must have been the last. - 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 == 5ando == 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 TrueJava
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