Knight Dialer Medium 0 attempts
LeetCode ↗

Knight Dialer

Medium Dynamic ProgrammingMemoization LeetCode

Imagine a chess knight set down on a phone keypad instead of a chessboard. Starting from any digit cell 0-9, it hops around using its usual L-shaped chess move, and each cell it lands on gets appended as a digit to the number being dialed. For a given length n, count how many distinct n-digit numbers the knight could produce this way. Since the count can get huge, return it modulo 10^9 + 7. Note that the knight has nowhere to jump from cell 5.

Input Format
Implement knightDialer(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
n = 1
Output
10

Example 2

Input
n = 2
Output
20
Constraints
  • 1 <= n <= 5000
Test Cases (2)
Case 1
Args: [1] Expected: 10
Case 2
Args: [2] Expected: 20
Topics
Dynamic ProgrammingMemoization

Approach: DP with Adjacency Map

Define the valid knight moves for each digit. For each step, accumulate the count of ways to reach each digit from its valid predecessor digits. Use a DP array that is updated iteratively.

javascript
function knightDialer(n) {
  const MOD = 1e9 + 7;
  const moves = {0:[4,6],1:[6,8],2:[7,9],3:[4,8],4:[0,3,9],5:[],6:[0,1,7],7:[2,6],8:[1,3],9:[2,4]};
  let dp = new Array(10).fill(1);
  for (let i = 1; i < n; i++) {
    const next = new Array(10).fill(0);
    for (let d = 0; d <= 9; d++)
      for (const m of moves[d]) next[d] = (next[d] + dp[m]) % MOD;
    dp = next;
  }
  return dp.reduce((a, b) => (a + b) % MOD, 0);
}

Time Complexity: O(n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript