Q48 Knight Probability in Chessboard - LeetCode 688

PHOTO

Fri Mar 31 2023 04:57:49 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    
    public boolean isValid(int ni , int nj , int n ){

        if(ni < 0 || nj < 0 || ni >= n || nj >= n)
        return false;

        return true;
    }
    public double knightProbability(int n, int k, int row, int col) {
        /* Q48 in dp playlist ,current represent current instance of the board,
        next represent next instance of the board in the end we swap curr &
        next and make next to 0 again so that we can use it store the prob of
        next moves which will impact the board cells

        in the end we loop over the latest board and add all the probibilites
        on all cell which will give us probibility that knight remains on the 
        board
        */

        double[][] curr = new double[n][n];
        double[][] next = new double[n][n];

        //making a direction array to loop over for the knights 8 moves
        int[][] dir = {{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};

        //for the very first instance probibility of center cell will be 1
        curr[row][col] = 1;

        //looping for k moves
        for(int moves = 0 ; moves < k ; moves++){
            
        //looping the current board and storing effect of knight move on next
            for(int i = 0 ; i < n ; i++ ){

                for(int j = 0 ; j < n ; j++){
                    
                    if(curr[i][j] != 0){
                        int ni = 0 , nj = 0;    //next i , next j
                        for(int d = 0 ; d < 8 ; d++){
                            ni = i + dir[d][0];
                            nj = j + dir[d][1];

                            if(isValid(ni,nj,n))
                            next[ni][nj] += curr[i][j]/8.0;
                        }
                    }
                }
            }
        //to store the probibilities of next move we do the following 
            curr = next;
            next = new double[n][n];
        }

        //now we add all the probibilites of the latest board and return it 
        double prob = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
            prob += curr[i][j];
        }

        return prob;
    }
}

https://leetcode.com/problems/knight-probability-in-chessboard/

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

DP level 2

@Ayush_dabas07

Q66 Distinct Echo Substrings - LeetCode 1316 (rabin karp rolling hash -> O(n^2)) Q66 Distinct Echo Substrings - LeetCode 1316(O(n^3) solution) Q65 Interleaving String - LeetCode 97 Q64 Frog Jump - LeetCode 403 Q63 Champagne Tower - LeetCode 799 Q62 Super Ugly Number - LeetCode 313 Q61 Ugly Number 2 - LeetCode 264 Q60 Minimum Insertion Steps to Make a String Palindrome - LeetCode 1316 Q59 Temple Offerings | Practice | GeeksforGeeks Q58 Word Break - LeetCode 139 Q57 Arithmetic Slices II - Subsequence - LeetCode 446 Q56 Arithmetic Slices - LeetCode 413 Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (tabulization) Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (memoization) Q54 Maximum Sum of 3 Non-Overlapping Subarrays - LeetCode 689 Q53 Maximum Sum of Two Non-Overlapping Subarrays - LeetCode 1031 Q52 Maximum difference of zeros and ones in binary string | Practice | GeeksforGeeks Q51 Mobile numeric keypad | Practice | GeeksforGeeks Q50 Distinct Transformation LeetCode Playground ( tabulization approach) Q50 - Distinct Transformation- LeetCode Playground ( recursion + memoization approach) Q49 Highway BillBoards - Coding Ninjas Codestudio approach 2 Q49 Highway BillBoards - Coding Ninjas Codestudio (approach 1 LIS) Q48 Knight Probability in Chessboard - LeetCode 688 Q47 Cherry Pickup - LeetCode 741 (recursion approach) Q46 Super Egg Drop - LeetCode 887 Q45 Predict the Winner - LeetCode 486 Q45 Optimal Strategy For A Game | Practice | GeeksforGeeks | leetcode 46 Q44 Largest Sum Subarray of Size at least K | Practice | GeeksforGeeks Q42 Maximum Subarray - LeetCode 53 Q41 Minimum Cost To Make Two Strings Identical | Practice | GeeksforGeeks Q40 Minimum ASCII Delete Sum for Two Strings - LeetCode 712 Q39 Scramble String - LeetCode 87 Q38 Edit Distance - LeetCode 72 Q37 Regular Expression Matching - LeetCode 10 Q36 Wildcard Matching - LeetCode Q35 Longest Repeating Subsequence | Practice | GeeksforGeeks Q34 Longest Common Substring | Practice | GeeksforGeeks Q33 Count Different Palindromic Subsequences - LeetCode 730 Q32 Number of distinct subsequences | Practice | GeeksforGeeks Q31 Longest Palindromic Substring - LeetCode Q30 Count Palindromic Subsequences | Practice | GeeksforGeeks Q29 Longest Palindromic Subsequence - LeetCode 516 Q28 Longest Common Subsequence - LeetCode 1143 Q27 Minimum Score Triangulation of Polygon - LeetCode 1039 Q26 Optimal binary search tree | Practice | GeeksforGeeks Q24 Matrix Chain Multiplication | Practice | GeeksforGeeks Q23 Palindrome Partitioning II - LeetCode 132 Q23 Palindrome Partitioning II - LeetCode - 132 ( n^3 approach) Q22 Palindromic Substrings - LeetCode 647 Q21 Rod Cutting | Practice | GeeksforGeeks Q20 Minimum Score Triangulation of Polygon - LeetCode 1039 Q19 Intersecting Chords in a Circle | Interviewbit Q18 Generate Parentheses - LeetCode 22 Q17 PepCoding | Count Of Valleys And Mountains Q16 Unique Binary Search Trees - LeetCode 96 Q15 Catalan Number Minimum Score of a Path Between Two Cities - 2492 Q14 Perfect Squares - LeetCode Q13 Russian Doll Envelopes - LeetCode (LIS in NlogN - accepted solution) Q13 Russian Doll Envelopes - LeetCode 354 solution1(LIS in O(n^2)) Q12 PepCoding | Maximum Non-overlapping Bridges Q11 Longest Bitonic subsequence | Practice | GeeksforGeeks Q10 Maximum sum increasing subsequence | Practice | GeeksforGeeks Q9 PepCoding | Print All Longest Increasing Subsequences Q8 Longest Increasing Subsequence - LeetCode 300 Q7 2 Keys Keyboard - LeetCode 650 Q-6 PepCoding | Print All Results In 0-1 Knapsack Q5 PepCoding | Print All Paths With Target Sum Subset Q4 PepCoding | Print All Paths With Maximum Gold Q3 PepCoding | Print All Paths With Minimum Cost Q2 Jump Game II - LeetCode 45 Q1 Maximal Square - LeetCode 221 Q67 Longest Increasing Subsequence - LeetCode 300 ( LIS O(nlogn) solution) Q43 K-Concatenation Maximum Sum - LeetCode 1191 Q13 Russian Doll Envelopes - LeetCode 354 ( LIS -> O(nlogn) solution) Q25 Burst Balloons - LeetCode 312

Browse more snippets >>