Knight Dialer
Medium · 1-D Dynamic Programming · Explanation and code example
Matrix Exponentiation
How it works
The transition from one step to the next can be represented as a matrix multiplication. If we encode the adjacency of knight jumps in a 10x10 matrix, then raising this matrix to the power n-1 gives us the count of paths of length n. Matrix exponentiation allows us to compute the result in O(log n) time, making this approach extremely efficient for very large n.
Steps
- Build a 10x10 transition matrix where
mat[i][j] = 1if a knight can jump from digitito digitj. - Use fast matrix exponentiation to compute
mat^(n-1). - Sum all entries in the result matrix to get the total count of
n-digit numbers.
Complexity
- Time complexity:
O(log n) - Space complexity:
O(1)
Things to watch for
Forgetting That Digit 5 Has No Valid Jumps
The knight cannot jump to any digit from position 5 on the phone dial pad. A common mistake is either forgetting to include digit 5 in the initial count (for n=1) or incorrectly assuming it contributes to longer sequences. For n >= 2, digit 5 effectively becomes a dead end and contributes nothing to the count.
Integer Overflow Without Modulo Operations
The number of valid phone numbers grows exponentially and quickly exceeds 32-bit integer limits. Failing to apply the modulo operation (10^9 + 7) after each addition leads to overflow. Apply modulo at every step where values are accumulated, not just at the final result.
Incorrect Jump Adjacency List
The knight's L-shaped movement on a phone dial creates a specific jump pattern that must be encoded correctly. Common mistakes include forgetting certain jumps (like 0 can reach 4 and 6) or adding invalid jumps (like 5 reaching any digit, or digits jumping to themselves). Double-check the adjacency list against the actual phone pad layout.
Python code example
from itertools import product
class Matrix:
def __init__(self, size):
self.n = size
self.a = [[0] * size for _ in range(size)]
def __mul__(self, other):
n = self.n
MOD = 10**9 + 7
product = Matrix(n)
for i in range(n):
for j in range(n):
for k in range(n):
product.a[i][k] = (product.a[i][k] + self.a[i][j] * other.a[j][k]) % MOD
return product
def matpow(mat, n, size):
res = Matrix(size)
for i in range(size):
res.a[i][i] = 1 # Identity matrix
while n:
if n & 1:
res = res * mat
mat = mat * mat
n >>= 1
return res
class Solution:
def knightDialer(self, n: int) -> int:
if n == 1:
return 10
MOD = 10**9 + 7
jumps = [
[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
[], [0, 1, 7], [2, 6], [1, 3], [2, 4]
]
mat = Matrix(10)
for i in range(10):
for j in jumps[i]:
mat.a[i][j] = 1
res = matpow(mat, n - 1, 10)
ans = sum(sum(res.a[i]) for i in range(10)) % MOD
return ans
C++ code example
class Matrix {
public:
vector<vector<int>> a;
int size;
static const int MOD = 1'000'000'007;
Matrix(int n) : size(n) {
a.assign(n, vector<int>(n, 0));
}
Matrix operator*(const Matrix &other) const {
Matrix product(size);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size; k++) {
product.a[i][k] = (product.a[i][k] + 1LL * a[i][j] * other.a[j][k]) % MOD;
}
}
}
return product;
}
};
Matrix matpow(Matrix mat, int n, int size) {
Matrix res(size);
for (int i = 0; i < size; i++) {
res.a[i][i] = 1; // Identity matrix
}
while (n > 0) {
if (n & 1) res = res * mat;
mat = mat * mat;
n >>= 1;
}
return res;
}
class Solution {
public:
int knightDialer(int n) {
if (n == 1) return 10;
vector<vector<int>> jumps = {
{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},
{}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
};
Matrix mat(10);
for (int i = 0; i < 10; i++) {
for (int j : jumps[i]) {
mat.a[i][j] = 1;
}
}
Matrix res = matpow(mat, n - 1, 10);
int ans = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
ans = (ans + res.a[i][j]) % Matrix::MOD;
}
}
return ans;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.