LeetCode 935: Knight Dialer

Problem Restatement

We place a chess knight on a phone keypad.

The keypad is arranged like this:

1 2 3
4 5 6
7 8 9
  0

The knight moves in the same L-shape as in chess.

We may start on any digit from 0 to 9.

Each time the knight lands on a digit, that digit is pressed.

Given an integer n, return how many distinct phone numbers of length n can be dialed.

Since the answer can be large, return it modulo:

10**9 + 7

The official statement asks for the number of length n phone numbers that can be dialed by starting on any digit and making n - 1 valid knight jumps.

Input and Output

Function shape:

class Solution:
    def knightDialer(self, n: int) -> int:
        ...

Examples

Example 1:

n = 1

We can choose any single digit.

There are 10 possible numbers:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Answer:

10

Example 2:

n = 2

We choose a starting digit, then make one knight jump.

The valid moves are:

0 -> 4, 6
1 -> 6, 8
2 -> 7, 9
3 -> 4, 8
4 -> 0, 3, 9
5 -> no moves
6 -> 0, 1, 7
7 -> 2, 6
8 -> 1, 3
9 -> 2, 4

There are 20 valid two-digit numbers.

Answer:

20

Example 3:

n = 3

The answer is:

46

These are the standard examples for this problem.

First Thought: Generate All Numbers

A direct approach is to try every possible starting digit and recursively follow every valid knight jump.

For each path of length n, we count one number.

This works for small n.

But the number of paths grows quickly. We do not need to build the actual numbers. We only need to count how many ways end at each digit after each length.

Key Insight

This is dynamic programming on a small graph.

Each digit is a node.

Each valid knight jump is an edge.

Let:

dp[digit]

mean the number of valid numbers of the current length that end at digit.

For length 1, every digit has exactly one way:

dp = [1] * 10

For each next length, we compute a new array.

If we are currently at digit d, then all counts at d can move to every digit in moves[d].

Algorithm

Use this move table:

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],
}

Initialize:

dp = [1] * 10

Then repeat n - 1 times:

1. Create next_dp = [0] * 10.
2. For each digit d, distribute dp[d] to every valid next digit.
3. Replace dp with next_dp.

Finally return:

sum(dp) % MOD

Walkthrough

Use:

n = 2

For length 1:

dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Each digit is one possible one-digit number.

Now build length 2.

From digit 0, we can go to 4 and 6.

So:

next_dp[4] += 1
next_dp[6] += 1

From digit 1, we can go to 6 and 8.

So:

next_dp[6] += 1
next_dp[8] += 1

After processing all digits, the total number of length 2 numbers is:

20

Correctness

For length 1, dp[digit] = 1 is correct because there is exactly one number of length 1 ending at each digit: the digit itself.

Assume dp[d] correctly stores the number of valid numbers of the current length ending at digit d.

To form a number with one more digit, the knight must jump from the current ending digit d to some valid next digit next_digit.

For each valid move d -> next_digit, every number counted in dp[d] creates one new valid number ending at next_digit.

The algorithm adds exactly those counts into next_dp[next_digit].

No invalid number is counted, because the algorithm only follows valid knight moves.

No valid number is missed, because every valid number of the next length has a previous digit and a final knight jump from that previous digit.

Therefore, after each iteration, dp contains the correct counts for that length.

After building length n, summing all entries gives the total number of valid phone numbers of length n.

Complexity

Implementation

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7

        moves = [
            [4, 6],
            [6, 8],
            [7, 9],
            [4, 8],
            [0, 3, 9],
            [],
            [0, 1, 7],
            [2, 6],
            [1, 3],
            [2, 4],
        ]

        dp = [1] * 10

        for _ in range(n - 1):
            next_dp = [0] * 10

            for digit in range(10):
                for next_digit in moves[digit]:
                    next_dp[next_digit] = (next_dp[next_digit] + dp[digit]) % MOD

            dp = next_dp

        return sum(dp) % MOD

Code Explanation

The modulo is required because the count can become very large:

MOD = 10**9 + 7

The move table stores valid knight jumps from each digit:

moves = [
    [4, 6],
    [6, 8],
    [7, 9],
    [4, 8],
    [0, 3, 9],
    [],
    [0, 1, 7],
    [2, 6],
    [1, 3],
    [2, 4],
]

The base case is length 1:

dp = [1] * 10

Every digit can be chosen as the first digit.

For each additional digit, we build a new DP array:

next_dp = [0] * 10

Then we distribute counts along valid moves:

for digit in range(10):
    for next_digit in moves[digit]:
        next_dp[next_digit] = (next_dp[next_digit] + dp[digit]) % MOD

Finally, all counts for length n are summed:

return sum(dp) % MOD

Testing

def run_tests():
    s = Solution()

    assert s.knightDialer(1) == 10
    assert s.knightDialer(2) == 20
    assert s.knightDialer(3) == 46
    assert s.knightDialer(4) == 104

    print("all tests passed")

run_tests()