Problem Description

You have a chess knight and a phone pad. The phone pad is arranged like this:

1 2 3
4 5 6
7 8 9
  0

A chess knight moves in an "L" shape - either 2 squares in one direction and 1 square perpendicular to that, or 1 square in one direction and 2 squares perpendicular to that.

The knight can only stand on numeric cells (0-9), not on the * and # keys.

Given an integer n, you need to find how many distinct phone numbers of length n can be dialed by the knight.

Rules:

• The knight can start on any numeric cell (0-9)
• To dial a number of length n, the knight makes exactly n-1 jumps
• Each jump must be a valid knight move
• All positions must be on numeric cells

For example, if the knight starts at 1, it can jump to either 6 or 8. If it starts at 5, it cannot make any valid moves since all knight moves from 5 would land outside the numeric cells.

The possible knight moves from each digit are:

• From 0: can move to 4, 6
• From 1: can move to 6, 8
• From 2: can move to 7, 9
• From 3: can move to 4, 8
• From 4: can move to 0, 3, 9
• From 5: no valid moves
• From 6: can move to 0, 1, 7
• From 7: can move to 2, 6
• From 8: can move to 1, 3
• From 9: can move to 2, 4

Return the total count of distinct phone numbers modulo 10^9 + 7 since the answer can be very large.

Intuition

The key insight is that this is a dynamic programming problem where we need to count paths of length n on the phone pad following knight movement rules.

Think about it this way: if we want to dial a number of length n, we need to make n-1 jumps starting from any digit. The total count of numbers we can dial depends on where we can reach after each jump.

Let's start with a simple observation - after placing the knight on any digit initially, we have 10 possible starting positions (digits 0-9). For a number of length 1, we simply have 10 possibilities (one for each starting digit).

For length 2, we need to consider: from each starting digit, where can the knight jump to? The count of 2-digit numbers ending at a particular digit equals the sum of counts from all digits that can reach it in one knight move.

This naturally leads to a recurrence relation. If we know how many ways we can reach each digit after i-1 jumps, we can calculate how many ways to reach each digit after i jumps.

For example, digit 0 can only be reached from digits 4 and 6 (based on knight moves). So if we know there are f[4] ways to reach digit 4 and f[6] ways to reach digit 6 after some jumps, then there are f[4] + f[6] ways to reach digit 0 after one more jump.

We can build this up iteratively: starting with the base case where each digit has count 1 (representing starting positions), we calculate the counts for the next step by summing up the counts from all positions that can reach each digit. We repeat this process n-1 times to get all possible n-digit numbers.

The beauty of this approach is that we don't need to track the actual numbers being dialed - we only care about the count of ways to reach each digit after a certain number of jumps.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with space optimization. The approach uses two arrays to track the count of ways to reach each digit.

Data Structure:

• f: An array of size 10 representing the count of ways to reach each digit (0-9) after the current number of jumps
• g: A temporary array to calculate the next state

Algorithm Steps:

1. Initialize the base case: Start with f = [1] * 10, meaning we can start at any of the 10 digits with count 1.

2. Iterate n-1 times to build numbers of length n:

   • Create a new array g = [0] * 10 to store the next state
   • For each digit, calculate how many ways we can reach it based on the previous state:

     g[0] = f[4] + f[6]        # Can reach 0 from 4 or 6
     g[1] = f[6] + f[8]        # Can reach 1 from 6 or 8
     g[2] = f[7] + f[9]        # Can reach 2 from 7 or 9
     g[3] = f[4] + f[8]        # Can reach 3 from 4 or 8
     g[4] = f[0] + f[3] + f[9] # Can reach 4 from 0, 3, or 9
     g[5] = 0                  # Cannot reach 5 (no incoming moves)
     g[6] = f[0] + f[1] + f[7] # Can reach 6 from 0, 1, or 7
     g[7] = f[2] + f[6]        # Can reach 7 from 2 or 6
     g[8] = f[1] + f[3]        # Can reach 8 from 1 or 3
     g[9] = f[2] + f[4]        # Can reach 9 from 2 or 4

   • Update f = g for the next iteration

3. Calculate the final result: Sum all values in f and take modulo 10^9 + 7

Why this works:

• After 0 jumps (length 1 numbers), we have 1 way to be at each digit
• After 1 jump (length 2 numbers), g[i] tells us how many 2-digit numbers end at digit i
• After n-1 jumps (length n numbers), f[i] tells us how many n-digit numbers end at digit i
• The total count is the sum of all possible ending positions

Time Complexity: O(n) - we iterate n-1 times, and each iteration does constant work Space Complexity: O(1) - we only use two arrays of fixed size 10

Example Walkthrough

Let's walk through finding all possible 3-digit numbers (n = 3) that can be dialed by the knight.

Initial Setup (n = 1):

• Start with f = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• This represents that we can start at any digit (0-9) with count 1

First Jump (building 2-digit numbers): We calculate where the knight can land after one jump from each starting position:

g[0] = f[4] + f[6] = 1 + 1 = 2         # Knight at 4→0 or 6→0
g[1] = f[6] + f[8] = 1 + 1 = 2         # Knight at 6→1 or 8→1
g[2] = f[7] + f[9] = 1 + 1 = 2         # Knight at 7→2 or 9→2
g[3] = f[4] + f[8] = 1 + 1 = 2         # Knight at 4→3 or 8→3
g[4] = f[0] + f[3] + f[9] = 1 + 1 + 1 = 3  # Knight at 0→4, 3→4, or 9→4
g[5] = 0                                # No way to reach 5
g[6] = f[0] + f[1] + f[7] = 1 + 1 + 1 = 3  # Knight at 0→6, 1→6, or 7→6
g[7] = f[2] + f[6] = 1 + 1 = 2         # Knight at 2→7 or 6→7
g[8] = f[1] + f[3] = 1 + 1 = 2         # Knight at 1→8 or 3→8
g[9] = f[2] + f[4] = 1 + 1 = 2         # Knight at 2→9 or 4→9

After first jump: f = [2, 2, 2, 2, 3, 0, 3, 2, 2, 2]

This means:

• 2 two-digit numbers end at 0 (40 and 60)
• 2 two-digit numbers end at 1 (61 and 81)
• 3 two-digit numbers end at 4 (04, 34, and 94)
• And so on...

Second Jump (building 3-digit numbers): Now we calculate the final positions after the second jump:

g[0] = f[4] + f[6] = 3 + 3 = 6         # 6 ways to reach 0
g[1] = f[6] + f[8] = 3 + 2 = 5         # 5 ways to reach 1
g[2] = f[7] + f[9] = 2 + 2 = 4         # 4 ways to reach 2
g[3] = f[4] + f[8] = 3 + 2 = 5         # 5 ways to reach 3
g[4] = f[0] + f[3] + f[9] = 2 + 2 + 2 = 6  # 6 ways to reach 4
g[5] = 0                                # Still no way to reach 5
g[6] = f[0] + f[1] + f[7] = 2 + 2 + 2 = 6  # 6 ways to reach 6
g[7] = f[2] + f[6] = 2 + 3 = 5         # 5 ways to reach 7
g[8] = f[1] + f[3] = 2 + 2 = 4         # 4 ways to reach 8
g[9] = f[2] + f[4] = 2 + 3 = 5         # 5 ways to reach 9

After second jump: f = [6, 5, 4, 5, 6, 0, 6, 5, 4, 5]

Final Result: Total count = 6 + 5 + 4 + 5 + 6 + 0 + 6 + 5 + 4 + 5 = 46

This means there are 46 distinct 3-digit phone numbers that can be dialed by the knight.

Some example paths:

• 1→6→0 (forms number 160)
• 3→4→0 (forms number 340)
• 7→2→9 (forms number 729)
• 0→4→3 (forms number 043)

The algorithm efficiently counts all such valid paths without actually generating the numbers themselves.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the input parameter representing the number of hops the knight makes. The algorithm uses a loop that iterates n - 1 times, and in each iteration, it performs a constant number of operations (calculating new values for 9 positions based on the previous values). Since each iteration takes O(1) time and we have n - 1 iterations, the overall time complexity is O(n).

The space complexity is O(1) or equivalently O(|Σ|) where |Σ| = 10, representing the number of digits on the dial pad. The algorithm uses two arrays f and g, each of fixed size 10, to store the number of ways to reach each digit. Since the size of these arrays is constant and doesn't depend on the input n, the space complexity is O(1). In the context of the problem, this can also be expressed as O(|Σ|) where Σ is the set of digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, making |Σ| = 10.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo During Intermediate Calculations

The Pitfall: The current solution only applies modulo at the very end when returning the result. For large values of n, the intermediate sums can overflow, causing incorrect results even though we're using Python which handles big integers. More importantly, in languages with fixed integer sizes (like Java or C++), this would cause integer overflow.

Why It Happens: Each iteration potentially multiplies the values by a factor related to the number of valid moves. After many iterations, these values grow exponentially large, which can lead to:

• Performance degradation due to handling very large numbers
• Integer overflow in languages with fixed-size integers
• Potential numerical instability

The Fix: Apply modulo operation after each calculation to keep numbers manageable:

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7
        current_count = [1] * 10
      
        for _ in range(n - 1):
            next_count = [0] * 10
          
            # Apply modulo after each calculation
            next_count[0] = (current_count[4] + current_count[6]) % MOD
            next_count[1] = (current_count[6] + current_count[8]) % MOD
            next_count[2] = (current_count[7] + current_count[9]) % MOD
            next_count[3] = (current_count[4] + current_count[8]) % MOD
            next_count[4] = (current_count[0] + current_count[3] + current_count[9]) % MOD
            next_count[6] = (current_count[0] + current_count[1] + current_count[7]) % MOD
            next_count[7] = (current_count[2] + current_count[6]) % MOD
            next_count[8] = (current_count[1] + current_count[3]) % MOD
            next_count[9] = (current_count[2] + current_count[4]) % MOD
          
            current_count = next_count
      
        return sum(current_count) % MOD

2. Misunderstanding the Problem: Confusing Number of Jumps with Number Length

The Pitfall: A common mistake is iterating n times instead of n-1 times. The problem asks for phone numbers of length n, which means:

• Starting position counts as the first digit (no jump needed)
• To create an n-digit number, we need exactly n-1 jumps

Example:

• For n=1: No jumps needed, we can start at any of the 10 digits → answer is 10
• For n=2: Need 1 jump from starting position → creates 2-digit numbers

The Fix: Always iterate n-1 times, not n times. The current solution correctly does this with for _ in range(n - 1).

3. Not Handling Edge Case n=1

The Pitfall: When n=1, the loop doesn't execute at all (since range(0) is empty), and we return the sum of the initial array, which is 10. While this is correct, it's important to understand why and potentially add explicit handling for clarity.

The Fix: Consider adding an explicit check for better code readability:

def knightDialer(self, n: int) -> int:
    if n == 1:
        return 10  # Can start at any digit for single-digit numbers
  
    MOD = 10**9 + 7
    # ... rest of the solution