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 updatet
based on the possible knight moves. For example,t[0]
is the sum of the ways to arrive at4
and6
fromf
, because a knight move can get you from4
or6
to0
. -
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 key5
is not reachable by the knight from any other key. -
After updating
t
, we assign its values tof
, and then we reusef
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
.
-
Initialize the array
f
to represent our starting point where all 10 digits (0-9) are possible starting positions withf=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
. -
As per our example, we'll perform
n-1 = 2
moves. -
For the first move, we use a temporary array
t
to calculate possible moves:-
To move to
0
, a knight could have come from4
or6
, sot[0] = f[4] + f[6] = 1 + 1 = 2
. -
To move to
1
, it could come from6
or8
, sot[1] = f[6] + f[8] = 1 + 1 = 2
, and so on for the rest of the digits, ensuringt[5]
remains0
. -
We end up with
t = [2, 2, 2, 2, 3, 0, 3, 2, 2, 2]
.
-
-
Then we copy
t
back tof
and proceed to the next move withf
now being[2, 2, 2, 2, 3, 0, 3, 2, 2, 2]
. -
Now, for the second (and final) move, we use the same process to update
t
using the newf
values. Each element oft
will represent the count of distinct phone numbers of length 3 ending with the respective digit. -
After these moves and computing the last
t
values given the knight movement restrictions, we could end up witht
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 onf
). -
Finally, we sum all the values (excluding
t[5]
which is0
) to find the total number of distinct 3-digit phone numbers we can dial. Assume our sum equalsS
. -
Since the problem instructs us to return the result modulo
10^9 + 7
, we computeS % (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
1class Solution:
2 def knightDialer(self, n: int) -> int:
3 # Base case: if there's only one move, the knight can be on any of the 10 digits
4 if n == 1:
5 return 10
6
7 # Initialization of the count array representing the knight's current position
8 counts = [1] * 10
9
10 # Loop to calculate the number of distinct phone numbers of length n
11 for _ in range(n - 1):
12 # Temporary array to store new counts after the knight moves
13 temp_counts = [0] * 10
14
15 # The knight moves to calculate the counts for each position
16 temp_counts[0] = counts[4] + counts[6]
17 temp_counts[1] = counts[6] + counts[8]
18 temp_counts[2] = counts[7] + counts[9]
19 temp_counts[3] = counts[4] + counts[8]
20 temp_counts[4] = counts[0] + counts[3] + counts[9]
21 # No 5 in the move set since the knight cannot move from digit 5 to any other digit
22 temp_counts[6] = counts[0] + counts[1] + counts[7]
23 temp_counts[7] = counts[2] + counts[6]
24 temp_counts[8] = counts[1] + counts[3]
25 temp_counts[9] = counts[2] + counts[4]
26
27 # Update counts for the next iteration
28 counts = temp_counts
29
30 # Return the sum of all the counts modulo 10^9 + 7 at the end of all moves
31 # This is done to handle large numbers, as required by the problem statement
32 return sum(counts) % (10**9 + 7)
33
1class Solution {
2 private static final int MOD = (int) 1e9 + 7;
3
4 public int knightDialer(int n) {
5 // If there's only one move, the knight can be on any of the 10 digits
6 if (n == 1) {
7 return 10;
8 }
9 // Initialize an array to track the number of unique phone numbers
10 long[] counts = new long[10];
11 Arrays.fill(counts, 1);
12
13 // Loop decrementing n to find unique numbers for each step
14 while (--n > 0) {
15 // Temporary array to hold the next state's number of unique phone numbers
16 long[] temp = new long[10];
17 // The knight on 0 can move to 4 or 6
18 temp[0] = counts[4] + counts[6];
19 // The knight on 1 can move to 6 or 8, etc.
20 temp[1] = counts[6] + counts[8];
21 temp[2] = counts[7] + counts[9];
22 temp[3] = counts[4] + counts[8];
23 temp[4] = counts[0] + counts[3] + counts[9];
24 // Skipping temp[5] as it's unreachable
25 temp[6] = counts[0] + counts[1] + counts[7];
26 temp[7] = counts[2] + counts[6];
27 temp[8] = counts[1] + counts[3];
28 temp[9] = counts[2] + counts[4];
29 // Updating the counts by taking modulo to prevent overflow
30 for (int i = 0; i < 10; ++i) {
31 counts[i] = temp[i] % MOD;
32 }
33 }
34 // Sum up all the unique phone numbers
35 long totalNumbers = 0;
36 for (long value : counts) {
37 totalNumbers = (totalNumbers + value) % MOD;
38 }
39 // Return the total count as an integer
40 return (int) totalNumbers;
41 }
42}
43
1using ll = long long;
2
3class Solution {
4public:
5 int knightDialer(int n) {
6 // Base case: If there's only one move, all the numbers [0-9] can be dialed once.
7 if (n == 1) return 10;
8
9 // Modulo used for avoiding integer overflow issues.
10 const int MOD = 1e9 + 7;
11
12 // Initialize a vector to keep track of the count of unique numbers
13 // that can be dialed from each digit on the keypad.
14 vector<ll> counts(10, 1ll); // Start with 1 move possible from each digit.
15
16 // Iterate over the number of hops minus 1 (since we've already initialized
17 // the first hop).
18 while (--n) {
19 vector<ll> tempCounts(10); // Temporary vector to compute the next state.
20
21 // Following lines update the count of unique numbers that can be dialed
22 // from each digit, based on the knight's move rules on the keypad.
23 tempCounts[0] = counts[4] + counts[6];
24 tempCounts[1] = counts[6] + counts[8];
25 tempCounts[2] = counts[7] + counts[9];
26 tempCounts[3] = counts[4] + counts[8];
27 tempCounts[4] = counts[0] + counts[3] + counts[9];
28 // There is no key 5 in the hop pattern, so it's skipped.
29 tempCounts[6] = counts[0] + counts[1] + counts[7];
30 tempCounts[7] = counts[2] + counts[6];
31 tempCounts[8] = counts[1] + counts[3];
32 tempCounts[9] = counts[2] + counts[4];
33
34 // Update the counts vector with the new values, applying the modulo operation.
35 for (int i = 0; i < 10; ++i) counts[i] = tempCounts[i] % MOD;
36 }
37
38 // Calculate the final answer as the sum of the counts modulo MOD.
39 ll ans = accumulate(counts.begin(), counts.end(), 0ll) % MOD;
40
41 return static_cast<int>(ans); // Cast the long long result to int before returning.
42 }
43};
44
1// Define type alias for long long equivalent in TypeScript
2type ll = number;
3
4// Define the constant MOD to prevent integer overflow
5const MOD: number = 1e9 + 7;
6
7// Initializes a vector to keep track of the count of unique numbers that can be dialed
8// from each digit on the keypad, with 1 move possible from each digit.
9let counts: ll[] = new Array(10).fill(1);
10
11// Function to compute the number of distinct phone numbers of length `n`
12// that can be dialed using a knight's moves on a standard 10-key keypad
13function knightDialer(n: number): number {
14 // Base case: With only one move, all numbers [0-9] can be dialed once.
15 if (n === 1) return 10;
16
17 // Iterate over the number of hops minus 1 (since we've already initialized
18 // the first hop).
19 while (--n) {
20 let tempCounts: ll[] = new Array(10).fill(0); // Temporary array for the next state.
21
22 // Update the count of unique numbers that can be dialed from each digit,
23 // based on the knight's move rules on the keypad.
24 tempCounts[0] = (counts[4] + counts[6]) % MOD;
25 tempCounts[1] = (counts[6] + counts[8]) % MOD;
26 tempCounts[2] = (counts[7] + counts[9]) % MOD;
27 tempCounts[3] = (counts[4] + counts[8]) % MOD;
28 tempCounts[4] = (counts[0] + counts[3] + counts[9]) % MOD;
29 // Digit 5 is not reachable by a knight's move, hence it's excluded.
30 tempCounts[6] = (counts[0] + counts[1] + counts[7]) % MOD;
31 tempCounts[7] = (counts[2] + counts[6]) % MOD;
32 tempCounts[8] = (counts[1] + counts[3]) % MOD;
33 tempCounts[9] = (counts[2] + counts[4]) % MOD;
34
35 // Copy the newly computed values back into the original counts array
36 counts = [...tempCounts];
37 }
38
39 // Calculate the final answer by summing the values in counts and applying the MOD.
40 let ans: ll = counts.reduce((acc, val) => (acc + val) % MOD, 0);
41
42 return ans; // Return the final count as an integer
43}
44
45// Example usage
46// const numberOfWays = knightDialer(2);
47// console.log(numberOfWays); // Output the number of unique numbers that can be dialed
48
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
andt
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.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.