LeetCode 935 - Knight Dialer

The problem asks us to count how many distinct phone numbers of length n can be generated by moving a chess knight across a numeric keypad. The keypad layout looks like this: A knight moves in an L-shape. From any current digit, it can jump only to specific other digits.

leetcodemediumdynamic-programming

LeetCode Problem 935

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many distinct phone numbers of length n can be generated by moving a chess knight across a numeric keypad.

The keypad layout looks like this:

1 2 3
4 5 6
7 8 9
  0

A knight moves in an L-shape. From any current digit, it can jump only to specific other digits. For example, from 1, the knight can move to 6 or 8. From 0, it can move to 4 or 6. The digit 5 is special because no valid knight move reaches or leaves it.

We are allowed to start on any digit. After choosing the starting digit, we perform exactly n - 1 knight jumps. Every sequence of visited digits forms a phone number of length n.

The input is a single integer n, representing the desired phone number length. The output is the total number of distinct valid sequences modulo 10^9 + 7.

The constraint 1 <= n <= 5000 is extremely important. A brute-force search that generates all sequences explicitly would grow exponentially and become impossible for large values like 5000. This strongly suggests that we need a dynamic programming approach where we reuse previously computed results instead of recomputing the same subproblems repeatedly.

Several edge cases matter immediately:

  • When n = 1, every digit is a valid phone number by itself, so the answer is 10.
  • Digit 5 has no outgoing knight moves, so after the first step it contributes nothing.
  • Because the answer can become enormous, every computation must apply modulo 10^9 + 7.
  • Since n can be as large as 5000, recursion without memoization would either time out or risk stack overflow.

Approaches

Brute Force Approach

A straightforward solution is to simulate every possible knight path recursively.

Starting from each digit, we try every valid knight move until we build a sequence of length n. Every completed sequence contributes 1 to the answer.

For example, if we start at 1, we can move to 6 or 8. From each of those digits, we again explore every valid move recursively.

This approach is correct because it explicitly enumerates every valid sequence exactly once. However, it performs enormous repeated work. The same subproblem appears repeatedly, such as:

  • "How many sequences of remaining length 7 start from digit 4?"
  • "How many sequences of remaining length 7 start from digit 4?" again from another path.

The total number of paths grows exponentially with n, making brute force completely impractical for n = 5000.

Optimal Dynamic Programming Approach

The key observation is that the problem has overlapping subproblems.

Suppose we know:

  • how many sequences of length k end at digit 0
  • how many sequences of length k end at digit 1
  • and so on

Then we can compute the counts for length k + 1 directly.

For example:

  • Any sequence ending at 0 must come from 4 or 6
  • Therefore:
next[0] = current[4] + current[6]

Instead of generating paths explicitly, we only track counts.

This transforms the exponential brute-force search into a linear dynamic programming solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) approximately O(n) recursion stack Explores every possible sequence explicitly
Optimal Dynamic Programming O(n) O(1) Tracks counts for each digit iteratively

Algorithm Walkthrough

Step 1: Define Knight Transitions

We first define which digits each digit can move to.

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]

This adjacency list models the keypad graph.

Step 2: Initialize DP State

We create an array where:

dp[digit] = number of sequences ending at this digit

For n = 1, every digit contributes exactly one sequence:

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

Step 3: Build Longer Sequences Iteratively

For each additional sequence length from 2 to n:

  1. Create a new array next_dp
  2. For every digit:
  • distribute its count to all reachable neighbors
  1. Apply modulo after every addition

Example:

If currently:

dp[1] = 5

then all sequences ending at 1 can extend to:

6 and 8

So:

next_dp[6] += 5
next_dp[8] += 5

Step 4: Replace Old State

After processing all digits:

dp = next_dp

Now dp represents counts for the next sequence length.

Step 5: Compute Final Answer

After completing all iterations:

answer = sum(dp) % MOD

This gives the total number of valid sequences of length n.

Why it works

The dynamic programming invariant is:

dp[d] = number of valid sequences of the current length ending at digit d

Every valid sequence of length k + 1 must come from a valid sequence of length k followed by one legal knight move. Since every transition is counted exactly once, the algorithm correctly counts all possible sequences without duplication or omission.

Python Solution

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

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

        dp = [1] * 10

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

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

            dp = next_dp

        return sum(dp) % MOD

The implementation begins by defining the knight movement graph as an adjacency list. This structure makes transitions efficient and easy to read.

The dp array stores how many sequences currently end at each digit. Initially, every digit contributes one sequence of length 1.

For each additional digit position, we create next_dp. Instead of building actual sequences, we propagate counts through valid knight moves. Every count transfer represents extending all sequences ending at one digit into new sequences ending at another digit.

After processing all transitions for a given length, dp is replaced with next_dp. This rolling-array technique keeps memory usage constant.

Finally, summing all entries gives the total number of valid phone numbers.

Go Solution

func knightDialer(n int) int {
    const MOD int = 1000000007

    moves := [][]int{
        {4, 6},       // 0
        {6, 8},       // 1
        {7, 9},       // 2
        {4, 8},       // 3
        {0, 3, 9},    // 4
        {},           // 5
        {0, 1, 7},    // 6
        {2, 6},       // 7
        {1, 3},       // 8
        {2, 4},       // 9
    }

    dp := make([]int, 10)

    for i := 0; i < 10; i++ {
        dp[i] = 1
    }

    for step := 0; step < n-1; step++ {
        nextDP := make([]int, 10)

        for digit := 0; digit < 10; digit++ {
            for _, neighbor := range moves[digit] {
                nextDP[neighbor] = (nextDP[neighbor] + dp[digit]) % MOD
            }
        }

        dp = nextDP
    }

    result := 0

    for _, count := range dp {
        result = (result + count) % MOD
    }

    return result
}

The Go implementation follows the same dynamic programming strategy as the Python version. The primary differences come from language syntax and type handling.

Go uses slices instead of Python lists, and we explicitly allocate arrays using make. Since Go integers can overflow depending on architecture, modulo operations are applied immediately after every addition.

The adjacency list is represented as a slice of slices, where each index corresponds to a keypad digit.

Worked Examples

Example 1

Input: n = 1

Initial state:

Digit Count
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1

No transitions are needed because the sequence length is already 1.

Final answer:

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10

Output:

10

Example 2

Input: n = 2

Initial state:

Digit Count
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1

After one transition:

Digit Incoming From Count
0 4, 6 2
1 6, 8 2
2 7, 9 2
3 4, 8 2
4 0, 3, 9 3
5 none 0
6 0, 1, 7 3
7 2, 6 2
8 1, 3 2
9 2, 4 2

Total:

2 + 2 + 2 + 2 + 3 + 0 + 3 + 2 + 2 + 2 = 20

Output:

20

Example 3

Input: n = 3131

The algorithm performs 3130 DP transitions while applying modulo at every step.

Final output:

136006598

The important detail here is that the DP solution remains efficient even for very large n.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each iteration processes 10 digits and a constant number of transitions
Space O(1) Only two arrays of size 10 are maintained

The keypad contains only 10 digits, and each digit has at most 3 outgoing moves. Therefore, every DP iteration performs a constant amount of work. Since we execute n - 1 iterations, the total runtime is linear in n.

The memory usage remains constant because we only store the current DP state and the next DP state, both fixed-size arrays of length 10.

Test Cases

sol = Solution()

assert sol.knightDialer(1) == 10  # single-digit numbers
assert sol.knightDialer(2) == 20  # example from problem statement
assert sol.knightDialer(3) == 46  # verifies multiple DP transitions
assert sol.knightDialer(4) == 104  # additional correctness check
assert sol.knightDialer(5) == 240  # larger transition depth
assert sol.knightDialer(10) == 14912  # stress intermediate growth
assert sol.knightDialer(3131) == 136006598  # large input from statement
assert sol.knightDialer(5000) >= 0  # maximum constraint
Test Why
n = 1 Validates base case behavior
n = 2 Confirms single transition correctness
n = 3 Verifies repeated DP updates
n = 4 Checks cumulative counting accuracy
n = 5 Ensures transitions remain consistent
n = 10 Tests moderate-sized input growth
n = 3131 Confirms modulo handling on huge counts
n = 5000 Validates maximum constraint performance

Edge Cases

One important edge case is n = 1. In this scenario, no knight moves occur at all. A common bug is accidentally running the transition loop once and producing incorrect counts. The implementation handles this naturally because the loop runs n - 1 times, which becomes zero iterations when n = 1.

Another important edge case involves digit 5. The knight cannot move to or from 5, so after the first transition its count should become zero permanently. A buggy adjacency list could accidentally allow transitions involving 5, inflating the answer. The implementation explicitly assigns an empty move list to 5, ensuring no invalid transitions occur.

A third critical edge case is very large values of n, such as 5000. Without modulo arithmetic, integer values would grow astronomically large and overflow fixed-width integer types in many languages. The implementation applies modulo 10^9 + 7 after every addition, guaranteeing safe arithmetic and compliance with the problem requirements.