Python 0794.py
class Solution:
def validTicTacToe(self, board: List[str]) -> bool:
o = 0
x = 0
for row in board:
for r in row:
if r == "O":
o += 1
elif r == "X":
x += 1
elif r != " ":
return False
# X starts
if x != o and x != o + 1:
return False
def won(player):
# vertical + horizontal
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
# diagonals
if board[0][0] == player and board[1][1] == player and board[2][2] == player:
return True
if board[2][0] == player and board[1][1] == player and board[0][2] == player:
return True
return False
# X can't have a triple if it's X's turn
if x == o:
if won("X"):
return False
# O can't have a triple if it's O's turn
if x == o + 1:
if won("O"):
return False
# both can't win at the same time
if won("X") and won("O"):
return False
return True
Difficulty
and has an acceptance rate of about 35% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Matrix
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation determines whether a given 3 × 3 Tic-Tac-Toe board configuration could arise from a sequence of legal moves. It proceeds by counting the marks, enforcing the alternating-turn rule, detecting winning lines for each player, and finally applying the logical constraints that define a reachable board state.
Counting Marks and Validating Characters
The first phase iterates over every cell of the board, incrementing separate counters for the two players and rejecting any character that is not a space, “X”, or “O”. The nested loops perform this work in a single pass, which avoids the need for multiple scans.
o = 0
x = 0
for row in board:
for r in row:
if r == "O":
o += 1
elif r == "X":
x += 1
elif r != " ":
return False
By returning immediately when an illegal character is encountered, the function eliminates further processing for obviously invalid inputs.
Enforcing Turn Order
After the counts are known, the code checks that the number of X’s is either equal to the number of O’s or exceeds it by exactly one, reflecting the rule that X always moves first and players alternate.
if x != o and x != o + 1:
return False
This single conditional captures both the “X starts” requirement and the alternating-turn invariant.
Detecting Winning Lines
A helper function won encapsulates the logic for detecting three identical marks in any row, column, or diagonal. The function iterates over the three indices, checking each horizontal and vertical line, then evaluates the two diagonal possibilities.
def won(player):
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[2][0] == player and board[1][1] == player and board[0][2] == player:
return True
return False
The function is called only when needed, and its result is cached implicitly by the surrounding logic, preventing redundant evaluations.
Turn-Specific Win Constraints
The algorithm applies the rule that a player cannot have already won on the opponent’s turn. When the counts indicate it is X’s turn (equal numbers of X and O), any existing X win invalidates the board. Conversely, when X has one extra move (it is O’s turn), an O win is disallowed.
if x == o:
if won("X"):
return False
if x == o + 1:
if won("O"):
return False
These checks ensure that a winning line appears only immediately after the player who created it has moved.
Mutual Exclusivity of Wins
A final condition guarantees that both players cannot simultaneously have winning lines, which is impossible under normal play.
if won("X") and won("O"):
return False
If this situation arises, the board is rejected.
Concluding Acceptance
When none of the earlier guard clauses trigger a False return, the board satisfies all structural and logical constraints, and the function returns True.
return True
Edge Cases Handled
The code correctly processes boards that contain only spaces, boards where one player has just completed a winning line, and configurations where the move count difference is at the extreme allowed values (0 or 1). It also rejects boards with extraneous characters, mismatched turn counts, premature wins, and the impossible scenario of both players winning.
Performance Optimizations
The implementation minimizes work by counting marks and validating characters in a single nested loop, eliminating the need for separate passes. Early returns are used aggressively: any violation of character validity, turn order, or win conditions aborts further computation. The won helper is invoked only when the turn count dictates that a win check is relevant, and the final mutual-win test reuses the same function without recomputing intermediate results. These choices keep the runtime bounded by a small constant factor, suitable for the fixed 3 × 3 board size.
ELI5 - Simplified Explanation
Imagine a tic-tac-toe board as a square grid where two friends take turns drawing shapes. One friend draws an X and the other draws an O. This code acts like a fair referee watching a game to see if the marks on the board could actually happen during a real game.
First, the code counts every single mark to make sure nobody cheated by taking extra turns. Since X always goes first, there should be either the same number of X and O marks or exactly one more X than O. If the count is wrong, the game is impossible.
Then, there is a helper function that looks for three marks in a row. It checks every row, every column, and both diagonal lines to see if a player has managed to get three in a row.
After that, the referee double-checks the rules one last time. If it is currently the turn for X, then it is impossible for X to have already won on the previous move, because the game would have ended sooner. The same rule applies to O. Finally, it makes sure both players did not win at the exact same moment, because that is impossible in a proper game. If everything follows these steps, then the game is valid.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Python | JS | Go | ||||
| LeetcodeHelp | C++ | Java | Python | ||||||
| Progiez | C++ | Java | Python | ||||||
| github | BigEggStudy | C# | |||||||
| black-shadows | C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| gouthampradhan | Java | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| varunu28 | Java | ||||||||
| wisdompeak | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| BigEggStudy | C# | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| gouthampradhan | Java | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| varunu28 | Java | ||||||||
| wisdompeak | C++ |
Videos
Similar Problems
- problem 348: Design Tic-Tac-Toe
Solved On The Same Day
- problem 812: Largest Triangle Area
- problem 824: Goat Latin
- problem 844: Backspace String Compare
- problem 791: Custom Sort String
- problem 807: Max Increase to Keep City Skyline
- problem 813: Largest Sum of Averages
- problem 814: Binary Tree Pruning
- problem 825: Friends Of Appropriate Ages
- problem 848: Shifting Letters
- problem 849: Maximize Distance to Closest Person
- problem 815: Bus Routes
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality