935. Knight Dialer

Problem Description

In this problem, you are presented with a chess knight placed on a standard 3x4 numeric keypad, where the knight can only stand on the numbered keys (1-9 and 0). The rules for the knight's movement are the same as in the chess game – it moves in an "L" shape, which means it can move two squares in one direction and then one square in a perpendicular direction. The task is to calculate the number of distinct phone numbers of a given length n that can be dialed with the knight starting from any number (i.e., making n-1 knight jumps). Since the number of distinct phone numbers could be very large, the answer should be returned modulo 10^9 + 7.

Intuition

To solve this problem, we use dynamic programming to keep track of the number of ways the knight can reach a certain key on the keypad after a certain number of moves. We initialize an array f where each index represents a digit on the keypad and the value at each index represents the number of ways to reach that digit. Initially, the knight can be on any digit, so each value in f is 1.

For each subsequent move (up to n-1 moves), we create a temporary array t to calculate the new number of ways to reach each digit from all other reachable digits, based on the unique movement pattern of the knight. Each entry t[i] is updated by adding the counts of the digits from which the knight can move to reach i, based on the possible knight moves. For instance, to reach digit 0, the knight could have come from digits 4 or 6, so t[0] is updated to the sum of f[4] and f[6].

We repeat this process n-1 times and then sum up the counts of all the keys in the final array t to get the total number of distinct phone numbers of length n. The sum is then taken modulo 10^9 + 7 to get the result within the required range.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to store the number of ways we can dial a number ending with each digit. Specifically, we know that each digit can be reached from one or more other digits. By repeatedly applying this knowledge, we can calculate the number of combinations leading to each digit step by step.

Here's an explanation of the flow of the algorithm:

• We begin with a list f of ten elements, each initialized to 1. This array represents the count of ways to reach every digit from 0 to 9 with zero knight moves (the starting position).

• For each move from the second (index 1) to the nth, we prepare a temporary array t, also with ten elements initialized to 0. This array will hold the number of ways to reach each digit after the current move.

• We iterate over all digits in f and update t based on the possible knight moves. For example, t[0] is the sum of the ways to arrive at 4 and 6 from f, because a knight move can get you from 4 or 6 to 0.

• The connections based on the keypad layout and knight moves are hardcoded in this logic:

  1t[0] = f[4] + f[6]
  2t[1] = f[6] + f[8]
  3t[2] = f[7] + f[9]
  4t[3] = f[4] + f[8]
  5t[4] = f[0] + f[3] + f[9]
  6t[6] = f[0] + f[1] + f[7]
  7t[7] = f[2] + f[6]
  8t[8] = f[1] + f[3]
  9t[9] = f[2] + f[4]

  Notice that t[5] is missing because the key 5 is not reachable by the knight from any other key.

• After updating t, we assign its values to f, and then we reuse f in the next iteration for subsequent moves.

• After all iterations (n-1 moves), we sum up the numbers in t, which by now contains the count of ways to finish dialing a number with a final move to each digit.

• We take the sum modulo 10**9 + 7 to ensure the final result fits within the integer range specified in the problem.

This algorithm employs dynamic programming to efficiently compute the possible number sequences, keeping only the counts of sequences ending in each digit rather than maintaining a list of all sequences. This dramatically reduces the space and time complexity of the solution, allowing it to work for large values of n.

Example Walkthrough

Let's say we want to calculate the number of distinct phone numbers that can be dialed with a knight's movement on a 3x4 numeric keypad and our phone numbers should be of length n = 3.

1. Initialize the array f to represent our starting point where all 10 digits (0-9) are possible starting positions with f=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1].

2. As per our example, we'll perform n-1 = 2 moves.

3. For the first move, we use a temporary array t to calculate possible moves:

   • To move to 0, a knight could have come from 4 or 6, so t[0] = f[4] + f[6] = 1 + 1 = 2.

   • To move to 1, it could come from 6 or 8, so t[1] = f[6] + f[8] = 1 + 1 = 2, and so on for the rest of the digits, ensuring t[5] remains 0.

   • We end up with t = [2, 2, 2, 2, 3, 0, 3, 2, 2, 2].

4. Then we copy t back to f and proceed to the next move with f now being [2, 2, 2, 2, 3, 0, 3, 2, 2, 2].

5. Now, for the second (and final) move, we use the same process to update t using the new f values. Each element of t will represent the count of distinct phone numbers of length 3 ending with the respective digit.

6. After these moves and computing the last t values given the knight movement restrictions, we could end up with t looking something like [5, 4, 4, 4, 8, 0, 8, 4, 4, 4] (the exact values would depend on the connections between the numbers based on f).

7. Finally, we sum all the values (excluding t[5] which is 0) to find the total number of distinct 3-digit phone numbers we can dial. Assume our sum equals S.

8. Since the problem instructs us to return the result modulo 10^9 + 7, we compute S % (10**9 + 7) to find the result within the required range.

In this illustrative example, the temporary array t helps keep track of the possible knight moves after each step, and the dynamic programming aspect efficiently reuses and updates f to represent the number of ways to reach each digit. The summed up values in t after n-1 moves yield the total number of distinct phone numbers that can be dialed, capturing the essence of the approach described in the provided content.

Solution Implementation

Time and Space Complexity

The given Python code defines a function knightDialer that calculates the number of distinct phone numbers of a certain length that can be dialed using the movements of a knight on a phone keypad.

Time Complexity

The time complexity of the knightDialer function is O(n), where n is the length of the phone number to dial. This is because the function contains a single loop that runs n - 1 times, and within each loop iteration, the operations are constant time assignments. There is also a sum operation after the loop, which takes O(10), i.e., constant time, because there are always 10 digits.

The time complexity is calculated as follows:

• Loop runs n - 1 times.
• Each loop operation is a constant time operation due to predetermined transitions between keypad digits.

There are no nested loops or recursive calls that would increase the complexity, so the overall time complexity remains linear with the input n.

Space Complexity

The space complexity of the knightDialer function is O(1), since the storage requirement does not scale with the input size n. The arrays f and t used in the function always have a fixed size of 10, which corresponds to the 10 digits in the phone keypad.

No additional space that grows with n is allocated during the computation, thus the space complexity is constant.

The space complexity is calculated as follows:

• Two fixed-size arrays f and t with size 10 each.
• Constant space for variables and loop iteration.

As a result, the amount of memory used does not depend on the input n, leading to a constant space complexity.

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