Python 0688.py
class Solution:
def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
board = []
for _ in range(n):
board.append([0] * n)
# initial position
board[row][column] = 1
# helper function
def add(b, x, y, what):
if 0 <= x < n and 0 <= y < n:
b[y][x] += what
for _ in range(k):
next = []
for _ in range(n):
next.append([0] * n)
for y in range(n):
for x in range(n):
have = board[y][x]
add(next, x - 2, y - 1, have)
add(next, x + 2, y - 1, have)
add(next, x - 2, y + 1, have)
add(next, x + 2, y + 1, have)
add(next, x - 1, y - 2, have)
add(next, x + 1, y - 2, have)
add(next, x - 1, y + 2, have)
add(next, x + 1, y + 2, have)
board = next
total = sum(sum(r) for r in board)
return total / 8 ** k
Difficulty
and has an acceptance rate of about 57% (300k+ submissions).
Typical patterns to solve this problem:
- Dynamic Programming
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 computes the probability that a knight, placed on an n × n chessboard at a given starting cell, remains on the board after making exactly k moves. It models the process as a discrete dynamic programming problem where each cell stores the number of ways the knight can arrive there after a certain number of moves. The final probability is obtained by normalizing the total count of surviving paths by the total number of possible move sequences, which is 8^k because a knight has up to eight legal moves at each step.
Board Initialization
The algorithm begins by constructing a two-dimensional list named board that represents the current distribution of the knight’s presence. Each row is created by appending a list of zeros of length n. The starting cell is then set to 1, indicating a single way to be at that position before any moves are taken.
board = []
for _ in range(n):
board.append([0] * n)
board[row][column] = 1
This explicit construction ensures that the board is a mutable grid of integers, ready for in-place updates during the simulation.
Helper Function for Safe Updates
A nested function add is defined to encapsulate the boundary check and the accumulation of ways into a target board. By checking that both coordinates lie within [0, n) before performing the addition, the function automatically discards moves that would land the knight off the board. This eliminates the need for separate conditional logic scattered throughout the main loop.
def add(b, x, y, what):
if 0 <= x < n and 0 <= y < n:
b[y][x] += what
The use of a local function reduces attribute lookups and keeps the inner loop concise.
Iterative Transition Over Moves
The core of the algorithm iterates k times, each iteration representing one knight move. For each step a fresh board called next is allocated, mirroring the dimensions of the original board and filled with zeros. This board will accumulate the number of ways to reach each cell after the current move.
for _ in range(k):
next = []
for _ in range(n):
next.append([0] * n)
The double nested loops over y and x traverse every cell of the current board. The variable have stores the number of ways the knight can be at the current cell before the move. The eight possible knight jumps are then applied by invoking add with the appropriate coordinate offsets. Because add silently ignores out-of-bounds coordinates, only legal destinations receive the accumulated count.
for y in range(n):
for x in range(n):
have = board[y][x]
add(next, x - 2, y - 1, have)
add(next, x + 2, y - 1, have)
add(next, x - 2, y + 1, have)
add(next, x + 2, y + 1, have)
add(next, x - 1, y - 2, have)
add(next, x + 1, y - 2, have)
add(next, x - 1, y + 2, have)
add(next, x + 1, y + 2, have)
After processing all cells, the reference board is updated to point to next, preparing for the next iteration. This swapping avoids the need to copy data between structures.
board = next
Final Probability Computation
When all k moves have been simulated, the algorithm aggregates the total number of surviving paths by summing every entry in the final board. The result is divided by 8 ** k, the total number of possible move sequences without regard to board boundaries, yielding the desired probability.
total = sum(sum(r) for r in board)
return total / 8 ** k
Edge Cases Handled
The implementation gracefully handles several boundary conditions:
- When
kis zero, the outer loop does not execute, leaving the board unchanged with a single1at the starting cell. The final sum equals1, and the division by8 ** 0(which is1) returns a probability of1.0, correctly reflecting that the knight has not moved. - For a board size of
1, any move would necessarily leave the board. Theaddfunction prevents any accumulation outside the single cell, resulting in a total of0after the first iteration and a probability of0.0for anyk > 0. - Starting positions on the edge or corner of the board are accommodated because each potential jump is individually validated by
add. Moves that would fall off the board are ignored, while legal moves contribute to the next state. - The code tolerates large values of
kwithout overflow concerns in Python, as integers have arbitrary precision and the division is performed using floating-point arithmetic only at the final step.
Performance Optimizations Observed
Several design choices contribute to efficient execution:
- Pre-allocation of the
boardandnextgrids avoids repeated resizing or dynamic list growth during the simulation. - The helper
addfunction centralizes the boundary check, reducing duplicated conditional statements and keeping the inner loop tight. - By storing the count of ways as integers and only converting to a floating-point value at the end, the algorithm minimizes the overhead associated with floating-point arithmetic during the iterative process.
- The use of local variables (
have,next,board) within the loops leverages Python’s fast local name resolution, which is faster than accessing attributes or globals. - The algorithm reuses the same variable name
nextfor each iteration, allowing the previous board to be garbage-collected promptly, which helps keep memory usage bounded by twon × ngrids regardless ofk.
ELI5 - Simplified Explanation
Imagine a big square game board filled with grass. There is a little horse piece called a knight standing on one of the squares. This code helps figure out where the horse might jump if it keeps hopping around for a while.
First, the computer creates the board and places the horse on its starting square. It shows this by putting a number one there to remember exactly where the horse begins.
Then, there is a special instruction called a helper function. This is like a game rule that checks if a jump lands inside the board or if it accidentally goes off the edge into the clouds. It makes sure the horse stays on the game board where it belongs.
Next, the computer starts a loop to help the horse make several jumps one after another. Since a horse can move in eight different ways shaped like an L, the code looks at every square on the board to see if the horse is there. For every place the horse could be, it calculates all the new squares where it can land next.
After it calculates all the possible places the horse can jump, it creates a brand new board for the next turn and clears the old one. It keeps repeating this move-calculation process until all the jumps allowed are finished.
At the very end, the computer adds up all the pieces left on the board to see how many paths the horse took, and it shares the final information about those jumps.
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 | Rust | Python | Go | TS | |||
| LeetcodeHelp | C++ | Java | Python | ||||||
| MemoryLimitExceeded | C++ | Python | |||||||
| Progiez | C++ | Java | Python | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fengvyi | C++ | ||||||||
| gouthampradhan | Java | ||||||||
| JoshCrozier | JS | ||||||||
| lkwq007 | Python | ||||||||
| MacJim | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| zfang399 | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fengvyi | C++ | ||||||||
| gouthampradhan | Java | ||||||||
| JoshCrozier | JavaScript | ||||||||
| lkwq007 | Python | ||||||||
| MacJim | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 576: Out of Boundary Paths
Solved On The Same Day
- problem 2000: Reverse Prefix of Word
- problem 1209: Remove All Adjacent Duplicates in String II
- problem 2295: Replace Elements in an Array
- problem 2414: Length of the Longest Alphabetical Continuous Substring
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