Knight Dialer

Medium
340.

Knight Dialer

Knight Dialer is a medium coding problem on dynamic programming, asked in Amazon, Google and Microsoft interviews.

A chess knight stands on a phone keypad laid out as

1 2 3
4 5 6
7 8 9
  0

The knight moves in its usual L shape and must land on a numbered key each time. Starting from any key and making exactly n - 1 moves dials a number of n digits.

Given n, return how many distinct numbers of length n can be dialled, modulo 10^9 + 7.

Example 1

Input
n = 1
Output
10
Explanation
Any single key.

Example 2

Input
n = 2
Output
20

Example 3

Input
n = 3
Output
46

Constraints

  • 1 <= n <= 500
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var knightDialer = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Knight Dialer — Solution in Python, Java & C++

Knight Dialer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on dynamic programming.

Knight Dialer is a medium coding problem on dynamic programming, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A chess knight stands on a phone keypad laid out as

1 2 3
4 5 6
7 8 9
  0

The knight moves in its usual L shape and must land on a numbered key each time. Starting from any key and making exactly n - 1 moves dials a number of n digits.

Given n, return how many distinct numbers of length n can be dialled, modulo 10^9 + 7.

Example 1

Input: n = 1
Output: 10
Explanation: Any single key.

Example 2

Input: n = 2
Output: 20

Example 3

Input: n = 3
Output: 46

Constraints

  • 1 <= n <= 500

Hints for Knight Dialer

  1. Hint 1

    Write down, for each key, the keys a knight can reach from it. Key 5 has none.

  2. Hint 2

    Let dp[d] be the number of valid dials of the current length that start at digit d; each extra digit is one redistribution along those moves.

  3. Hint 3

    Every one of the ten keys is a legal starting point, so the answer sums the whole array.

How to solve Knight Dialer

List the knight moves from each key; dp[d] is the number of valid dials of the current length starting at d, and each extra digit sums the counts of the keys reachable from d.

Approach

  1. Start dp = [1] * 10.
  2. Repeat n - 1 times: nxt[d] = Σ dp[to] over to in moves[d], modulo 10⁹+7.
  3. Return the sum of dp.

Why it works

A dial of length L starting at d is d followed by a dial of length L-1 starting at a neighbour, so the counts compose along the move graph. The graph is symmetric, so counting by start or by end gives the same totals.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Key 5 has no moves — it contributes 1 for n = 1 and 0 afterwards.

Reference solution

Python

def knightDialer(n: int) -> int:
    MOD = 1000000007
    moves = [[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4]]
    dp = [1] * 10
    for _ in range(n - 1):
        nxt = [0] * 10
        for digit in range(10):
            for to in moves[digit]:
                nxt[digit] = (nxt[digit] + dp[to]) % MOD
        dp = nxt
    return sum(dp) % MOD

Java

public static int knightDialer(int n) {
    final int MOD = 1000000007;
    int[][] moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
    int[] dp = new int[10];
    Arrays.fill(dp, 1);
    for (int step = 1; step < n; step++) {
        int[] next = new int[10];
        for (int digit = 0; digit < 10; digit++) {
            for (int to : moves[digit]) {
                next[digit] = (next[digit] + dp[to]) % MOD;
            }
        }
        dp = next;
    }
    int total = 0;
    for (int d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
    return total;
}

C++

int knightDialer(int n) {
    const int MOD = 1000000007;
    vector<vector<int>> moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
    vector<int> dp(10, 1);
    for (int step = 1; step < n; step++) {
        vector<int> next(10, 0);
        for (int digit = 0; digit < 10; digit++) {
            for (int to : moves[digit]) {
                next[digit] = (next[digit] + dp[to]) % MOD;
            }
        }
        dp = next;
    }
    int total = 0;
    for (int d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
    return total;
}

JavaScript

var knightDialer = function(n) {
    const MOD = 1000000007;
    const moves = [[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4]];
    let dp = new Array(10).fill(1);
    for (let step = 1; step < n; step++) {
        const next = new Array(10).fill(0);
        for (let digit = 0; digit < 10; digit++) {
            for (let k = 0; k < moves[digit].length; k++) {
                next[digit] = (next[digit] + dp[moves[digit][k]]) % MOD;
            }
        }
        dp = next;
    }
    let total = 0;
    for (let d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming