Leetcode: Knight Probability in Chessboard: Iterative Solution

Problem Description

Problem description is given in Leetcode: Knight Probability in Chessboard.

Iterative Solution

At each position a knight may go to 8 new positions. Probability of moving to a new position is probability of being at current position divided by 8. Thus we can iteratively calculate probabilities for each move. After last move, we can take sum of all probabilities which gives total probability of staying on board.

The knight starts at row r and column c in a board of NxN. K shows total moves, k shows kth move. Probability of being on board at kth move is given by function f.

S contains all previous positions where the knight can move from to position (r,c).

At start where k=0;

Implementation

For initial position probability is set to 1. Since older probabilities are not needed, only two arrays (dp and dpNext) are used to keep current and previous probabilities. After each move arrays are swapped.

Next positions are calculated using dr and dc arrays. Obviously the arrays contain 8 elements which are used to calculate all possible 8 next positions. Off-board positions are ignored.

After the final move, sum of all probabilities is returned.

class Solution {

    public double knightProbability(int N, int K, int r, int c) {
        return iterativeFindProbability(N, K, r,c);
    }
    
    public double iterativeFindProbability(int N, int K, int r, int c){
        double[][] dp = new double[N][N];
        
        int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
        int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};
        
        dp[r][c] = 1.0;
        
        while(K-->0){
            double[][] dpNext = new double[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    for(int m=0;m<8;m++){
                        int mi = i+dr[m];
                        int mj = j+dc[m];
                        if(areWeOnBoard(N, mi, mj)){
                            dpNext[mi][mj] += dp[i][j]/8; 
                        }
                    }
                }
            }
            
            dp = dpNext;
        }
        
        return sum(dp);
    }
    
    public double sum(double[][] arr){
        double sum=0.0;
        for(double arr1[] : arr)
            for(double a: arr1)
                sum+=a;
        
        return sum;
    }

    public boolean areWeOnBoard(int N, int r, int c){
        if(r<N && r>=0 && c<N && c>=0)
            return true;
        
        return false;
    }
}

Complexity

Space complexity is . Time complexity is . After each move, all probabilities are calculated using probabilities from 8 previous positions.