algoadvance

Leetcode 688. Knight Probability in Chessboard

Problem Statement

You are given an N x N chessboard and a knight is placed on the board at a given position (r, c). The knight has K moves, and at each move, it can move to one of the 8 possible positions as described below. A knight’s move is L-shaped: it can move two squares in one direction and then move one square perpendicular to that direction.

You need to find the probability that the knight remains on the board after making K moves.

Possible Moves of Knight:

Function Signature:

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

Example:

Input:

N = 3, K = 2, r = 0, c = 0

Output:

0.0625

Explanation:

Clarifying Questions

  1. Initial Position: Is the initial position always valid (i.e., within bounds of the N x N chessboard)?
  2. Constraints: Any constraints on the values for N, K, r, and c?
  3. Edge Cases: What should be returned if the knight already starts off the board (though it seems the initial position is guaranteed valid)?

Strategy

  1. DP Initialization: We’ll use a memoization/dynamically programmed approach where we keep an array memo[K+1][N][N] to store the probability of being on the board at cell [r][c] after k moves.
  2. Handling Moves: We’ll iteratively compute probabilities from k=1 to K starting with the base case probability 1 at k=0 if within bounds.
  3. Summing Probabilities: The knight can move to 8 possible directions, for each position and each number of remaining moves, sum all probabilities from next positions iteratively.

Time Complexity

Code

public class KnightProbabilityInChessboard {
    private static final int[][] DIRECTIONS = {
        {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
        {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
    };

    public double knightProbability(int N, int K, int r, int c) {
        double[][][] memo = new double[K+1][N][N];
        // Initial position probability is 1
        memo[0][r][c] = 1;

        for (int k = 1; k <= K; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (memo[k-1][i][j] > 0) {
                        for (int[] dir : DIRECTIONS) {
                            int ni = i + dir[0];
                            int nj = j + dir[1];
                            if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
                                memo[k][ni][nj] += memo[k-1][i][j] / 8.0;
                            }
                        }
                    }
                }
            }
        }

        double probability = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                probability += memo[K][i][j];
            }
        }
        return probability;
    }

    public static void main(String[] args) {
        KnightProbabilityInChessboard solution = new KnightProbabilityInChessboard();
        System.out.println(solution.knightProbability(3, 2, 0, 0));  // Output: 0.0625
    }
}

This solution initializes the DP table and iterates through each step to compute the probability of the knight remaining on the board. Finally, it sums up probabilities for all positions after K moves.

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