Meta / Amazon / Google / Microsoft Interview | Knight Probability in Chessboard Solution | LeetCode-688: Medium | JavaScript Implementation

Implementation:

var knightProbability = function (n, k, row, column) {
let totalCount = Math.pow(8, k);
let totalSafeMoves = 0;
let memo = [];
let directions = [
[1, -2],
[1, 2],
[2, -1],
[2, 1],
[-2, 1],
[-2, -1],
[-1, 2],
[-1, -2],
];
const isValid = (i, j) => {
if (i >= 0 && i < n && j >= 0 && j < n) {
return true;
} else {
return false;
}
};
const util = (i, j, possibleMoves) => {
if (!isValid(i, j)) {
return 0;
} else if (possibleMoves == k) {
return 1;
} else {
if (memo[i] && memo[i][j] != null && memo[i][j][possibleMoves]!=null) {
return memo[i][j][possibleMoves];
}
if (!memo[i]) {
memo[i] = [];
}
if(!memo[i][j]){
memo[i][j] = [];
}
memo[i][j][possibleMoves] = 0;
directions.forEach((delta) => {
let newX = i + delta[0];
let newY = j + delta[1];
memo[i][j][possibleMoves] = memo[i][j][possibleMoves] + util(newX, newY, possibleMoves + 1);
});
return memo[i][j][possibleMoves];
}
};
totalSafeMoves = util(row, column, 0);
return totalSafeMoves / totalCount;
}
console.log(knightProbability(3, 3, 0, 0));
//Output: 0.06250

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store