LeetCode 688: Knight Probability in Chessboard Solution

Master LeetCode problem 688 (Knight Probability in Chessboard), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

688. Knight Probability in Chessboard

Medium

Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with a 3D array to keep track of the probabilities of the knight being on the board at each cell after each move. We will iteratively calculate the probabilities for each cell after every move until reaching the kth move. Finally, we sum up the probabilities of all cells that are still on the board.

Initialize a 3D array dp of size (n x n x k+1) where dp[i][j][step] represents the probability of the knight being at cell (i, j) after step moves.
For the base case where step = 0, set dp[row][col][0] = 1 as the knight is already at the starting position.
For each step from 1 to k, iterate over all cells and calculate the probabilities based on the previous step's probabilities and the knight's possible moves.
The knight can move to 8 different positions from a cell, with each move having a probability of 1/8. If the move is within the board, update the probability for the new position.
After k moves, sum up the probabilities of all cells that are still on the board to get the final result.

Time Complexity: O(n^2 * k)
Space Complexity: O(n^2 * k)

Solution Code

class Solution {
    public double knightProbability(int n, int k, int row, int col) {
        int[][] directions = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
        double[][][] dp = new double[n][n][k + 1];
        
        dp[row][col][0] = 1;
        
        for (int step = 1; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] dir : directions) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < n && y >= 0 && y < n) {
                            dp[i][j][step] += dp[x][y][step - 1] / 8.0;
                        }
                    }
                }
            }
        }
        
        double result = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result += dp[i][j][k];
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 688 (Knight Probability in Chessboard)?

This page provides optimized solutions for LeetCode problem 688 (Knight Probability in Chessboard) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 688 (Knight Probability in Chessboard)?

The time complexity for LeetCode 688 (Knight Probability in Chessboard) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 688 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 688 in Java, C++, or Python.

Back to LeetCode Solutions