algoadvance

Leetcode 688. Knight Probability in Chessboard

Problem Statement

The problem is to determine the probability that a knight stays on an N x N chessboard after making exactly K moves, starting from position (r, c).

A knight in chess has eight possible moves. If the knight moves off the board, it is no longer considered. We have to find the probability that the knight stays on the board after K moves.

Function Signature

double knightProbability(int N, int K, int r, int c);

• N is the dimension of the chessboard.
• K is the number of moves the knight will make.
• r and c are the starting row and column of the knight.

Example

knightProbability(3, 2, 0, 0); // returns 0.0625

knightProbability(3, 1, 0, 0); // returns 0.25

Clarifying Questions

1. Is the input always valid?
   • Yes, assume that N, K, r, and c are always within reasonable bounds such that no invalid accesses occur.
2. What are the constraints on N, K, r, and c?
   • The exact constraints are not explicitly given, but typically N will be for a standard chessboard, i.e., a range between 1 <= N <= 25, and 0 <= r, c < N.
3. What precision is required for the result?
   • Generally a double with precision up to 1e-5 should be fine.

Strategy

1. Dynamic Programming:
   • We can use dynamic programming to keep track of probabilities of the knight being on each cell after each move.
   • Create a 3D array dp where dp[k][i][j] represents the probability of being on cell (i, j) after k moves.
   • Initialize dp[0][r][c] = 1.0 as the starting position.
   • For each move from 0 to K-1, update the probabilities based on the knight’s possible moves.
2. Possible Moves:
   • Define the 8 possible moves a knight can make as a list of row and column offsets.
3. Boundary Checks:
   • Each time a move is made, ensure that the knight remains within the bounds of the board.
4. Sum Probabilities:
   • After K moves, sum up the probabilities that the knight is still on the board to get the final result.

Code

#include <vector>

using namespace std;

class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        // Direction vectors for knight moves
        vector<vector<int>> directions = \{\{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
        
        // DP table
        vector<vector<vector<double>>> dp(K + 1, vector<vector<double>>(N, vector<double>(N, 0.0)));
        
        // Initial position
        dp[0][r][c] = 1.0;
        
        // Fill DP table
        for (int k = 1; k <= K; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (dp[k - 1][i][j] > 0) {
                        for (const auto& direction : directions) {
                            int ni = i + direction[0];
                            int nj = j + direction[1];
                            if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
                                dp[k][ni][nj] += dp[k - 1][i][j] / 8.0;
                            }
                        }
                    }
                }
            }
        }
        
        // Calculate the total probability the knight is still on the board after K moves
        double probability = 0.0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                probability += dp[K][i][j];
            }
        }
        
        return probability;
    }
};

Time Complexity

• The time complexity of this solution is (O(K \times N^2 \times 8)), simplifying to (O(K \times N^2)) because for each of the K moves, we update each cell (i, j) based on constant number (8) of possible previous positions.
• The space complexity is (O(K \times N^2)) to keep the DP table.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?