On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).
A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.
Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly k moves or has moved off the chessboard.
Return the probability that the knight remains on the board after it has stopped moving.
Example 1:
Input: n = 3, k = 2, row = 0, column = 0 Output: 0.06250 Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board. From each of those positions, there are also two moves that will keep the knight on the board. The total probability the knight stays on the board is 0.0625.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0 Output: 1.00000
Constraints:
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1The Knight Probability in Chessboard problem asks for the probability that a knight remains on an n x n chessboard after making k moves from a starting position. The key observation is that a knight has 8 possible moves, and each move has equal probability.
This problem is best approached using Dynamic Programming. Define a DP state such as dp[m][r][c] representing the probability of the knight being on cell (r, c) after m moves. For each step, distribute the probability from the current cell to all valid knight moves. If a move goes outside the board, that probability is discarded.
You can implement this using top-down memoization or a bottom-up DP approach to iteratively update probabilities. Since each state considers up to 8 transitions, the overall time complexity becomes proportional to the number of moves and board cells.
This structured state transition makes the problem a classic example of probabilistic dynamic programming.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Top-Down Memoization) | O(k * n^2) | O(k * n^2) |
| Dynamic Programming (Bottom-Up) | O(k * n^2) | O(n^2) |
Pepcoding
In this approach, we utilize a 3D array `dp` where `dp[k][i][j]` represents the probability that the knight is on position `(i, j)` after making `k` moves. Initially, the knight is placed at `(row, column)`, so `dp[0][row][column] = 1`. For each move `k`, we calculate the probability of the knight being on each cell `(i, j)` by summing over probabilities of positions that can move to `(i, j)` in one knight move.
This involves iterating through each cell and updating the probabilities according to knight's possible moves.
Time Complexity: O(k * n^2), as each position on the board and each move is processed.
Space Complexity: O(k * n^2), for storing the DP states.
1#include <stdio.h>
2
3#define MAX 25
4
5double knightProbability(int n, int k, int row,
The code initializes a 3D dynamic array `dp` for storing the probabilities of being on each board position `(i, j)` after `k` moves. We iterate through each move and potential knight positions, updating probabilities based on possible knight moves.
This approach leverages recursion along with memoization to optimize calculations. We define a recursive function to calculate the probability the knight remains within bounds after `k` moves. We utilize memoization to cache results of subproblems to avoid redundant calculations. If the knight's position ends within the board boundaries, it contributes to the final probability.
Time Complexity: O(k * n^2).
Space Complexity: O(k * n^2).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is representative of the type of dynamic programming and probability-based questions sometimes asked in FAANG-style interviews. It tests state transitions, DP optimization, and careful handling of boundary conditions.
A 2D or 3D dynamic programming array is typically used to store probabilities for board positions and move counts. Some optimized solutions use two 2D arrays to represent the current and next states, reducing space usage.
The optimal approach uses dynamic programming to track the probability of the knight being on each cell after every move. By updating probabilities for all 8 possible knight moves at each step, we avoid redundant calculations and efficiently compute the final probability.
Dynamic programming works well because the probability of reaching a cell after a certain number of moves depends on previously computed states. By storing and reusing these intermediate results, we avoid recomputation and significantly improve efficiency.
C implementation uses recursion with memoization to solve the problem. The `memo` table caches results for specific `(i, j, k)` states to avoid redundant computations.