Knight Dialer — Solution in Python, Java & C++
Knight Dialer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on dynamic programming.
Knight Dialer is a medium coding problem on dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A chess knight stands on a phone keypad laid out as
1 2 3
4 5 6
7 8 9
0
The knight moves in its usual L shape and must land on a numbered key each time. Starting from any key and making exactly n - 1 moves dials a number of n digits.
Given n, return how many distinct numbers of length n can be dialled, modulo 10^9 + 7.
Example 1
Input: n = 1
Output: 10
Explanation: Any single key.
Example 2
Input: n = 2
Output: 20
Example 3
Input: n = 3
Output: 46
Constraints
1 <= n <= 500
Hints for Knight Dialer
Hint 1
Write down, for each key, the keys a knight can reach from it. Key 5 has none.
Hint 2
Let
dp[d]be the number of valid dials of the current length that start at digitd; each extra digit is one redistribution along those moves.Hint 3
Every one of the ten keys is a legal starting point, so the answer sums the whole array.
How to solve Knight Dialer
List the knight moves from each key; dp[d] is the number of valid dials of the current length starting at d, and each extra digit sums the counts of the keys reachable from d.
Approach
- Start
dp = [1] * 10. - Repeat
n - 1times:nxt[d] = Σ dp[to]overtoinmoves[d], modulo10⁹+7. - Return the sum of
dp.
Why it works
A dial of length L starting at d is d followed by a dial of length L-1 starting at a neighbour, so the counts compose along the move graph. The graph is symmetric, so counting by start or by end gives the same totals.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Key 5 has no moves — it contributes 1 for
n = 1and 0 afterwards.
Reference solution
Python
def knightDialer(n: int) -> int:
MOD = 1000000007
moves = [[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4]]
dp = [1] * 10
for _ in range(n - 1):
nxt = [0] * 10
for digit in range(10):
for to in moves[digit]:
nxt[digit] = (nxt[digit] + dp[to]) % MOD
dp = nxt
return sum(dp) % MODJava
public static int knightDialer(int n) {
final int MOD = 1000000007;
int[][] moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
int[] dp = new int[10];
Arrays.fill(dp, 1);
for (int step = 1; step < n; step++) {
int[] next = new int[10];
for (int digit = 0; digit < 10; digit++) {
for (int to : moves[digit]) {
next[digit] = (next[digit] + dp[to]) % MOD;
}
}
dp = next;
}
int total = 0;
for (int d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
return total;
}C++
int knightDialer(int n) {
const int MOD = 1000000007;
vector<vector<int>> moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
vector<int> dp(10, 1);
for (int step = 1; step < n; step++) {
vector<int> next(10, 0);
for (int digit = 0; digit < 10; digit++) {
for (int to : moves[digit]) {
next[digit] = (next[digit] + dp[to]) % MOD;
}
}
dp = next;
}
int total = 0;
for (int d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
return total;
}JavaScript
var knightDialer = function(n) {
const MOD = 1000000007;
const moves = [[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4]];
let dp = new Array(10).fill(1);
for (let step = 1; step < n; step++) {
const next = new Array(10).fill(0);
for (let digit = 0; digit < 10; digit++) {
for (let k = 0; k < moves[digit].length; k++) {
next[digit] = (next[digit] + dp[moves[digit][k]]) % MOD;
}
}
dp = next;
}
let total = 0;
for (let d = 0; d < 10; d++) total = (total + dp[d]) % MOD;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming