Knight Dialer

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagram:

A chess knight can move as indicated in the chess diagram below:

Given an integer n, return how many distinct phone numbers of length n we can dial.

You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps.

As the answer may be very large, return the answer modulo 10<sup>9</sup> + 7.

Example 1:

Input: n = 1
Output: 10
Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2:

Input: n = 2
Output: 20
Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Example 3:

Input: n = 3131
Output: 136006598
Explanation: Please take care of the mod.

Constraints:

• 1 <= n <= 5000

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  # Initialize dp array with 1 for n = 1

        for _ in range(1, n):
            new_dp = [0] * 10
            for i in range(10):
                for next_num in moves[i]:
                    new_dp[next_num] = (new_dp[next_num] + dp[i]) % MOD
            dp = new_dp
        
        return sum(dp) % MOD

Explanation:

1. Problem Understanding:

   • The problem requires us to find the number of distinct phone numbers of length n that can be dialed using a knight's moves on a phone keypad.
   • The knight can start at any digit and perform n-1 jumps.
   • The result should be modulo 10^9 + 7.

2. Approach:

   • We can solve this problem using dynamic programming.
   • We define dp[i] as the number of distinct phone numbers of a certain length that end at digit i.
   • We iterate from length 1 to n, updating the dp array at each step based on the knight's possible moves.

3. Code Implementation:

   • We define a dictionary moves that stores the possible knight moves from each digit.
   • The dp array is initialized with 1s because for n=1, each digit can be the start of a valid phone number.
   • For each length from 2 to n, we calculate the new dp array by summing the counts from the previous dp array based on the possible knight moves.
   • Finally, we sum the values in the dp array and take the modulo to get the final result.

Example:

Let's trace the execution for n = 2:

• Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• For the first jump:
  • new_dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • new_dp[4] += dp[0] = 1
  • new_dp[6] += dp[0] = 1
  • new_dp[6] += dp[1] = 1
  • new_dp[8] += dp[1] = 1
  • ...
  • After iterating through all digits, new_dp becomes [2, 2, 2, 2, 3, 0, 3, 2, 2, 2]
• Sum of new_dp is 20, which is the number of distinct phone numbers of length 2.

Big(O) Runtime Analysis:

• The outer loop iterates n times (from 1 to n).
• The inner loop iterates 10 times (for each digit).
• Inside the inner loop, we iterate over the possible moves for each digit, which is constant time (at most 3 or 4 moves).
• Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis:

• We use a dp array of size 10 to store the counts for each digit.
• We use a moves dictionary to store the possible moves, which is constant size.
• Therefore, the overall space complexity is O(1) (constant space).

Edge Cases:

1. n = 1: The function correctly returns 10, as any digit is a valid phone number of length 1.
2. n = 2: The function returns the correct count of distinct phone numbers of length 2.
3. n is a large number: The modulo operation ensures that the result does not overflow, and the dynamic programming approach efficiently calculates the result.