Leetcode 935. Knight Dialer
Problem Explanation
This problem is a 'Knight Dialer' problem. A knight in chess is known for its unconventional movement. It moves two spaces forward and one space orthogonal to this. This problem implies the same kind of movement to a dial pad, where a knight can make N
hops from one key to another. Each time it hops and lands on a key, it presses the key and the number gets dialed.
The problem is to find out how many distinct numbers can be dialed in this manner. Since the answer could be large, the output would be the answer modulo 10^9 + 7
.
Walkthrough
For instance, if the knight only has to move 1
time, it can dial 10
distinct numbers, where it doesn't actually move but just press the initial number. For 2
hops, the knight can dial 20
distinct numbers. It can jump from 0
to 4
, and 6
or from 1
to 6
or 8
or from 3
to 4
, or 8
or again from 7
to 2
or 6
and so on. So, it makes a total of 20 distinct numbers that can be dialed.
Solution Approach
The above problem can be solved using dynamic programming. The idea is to compute dp[i][j]
โ total count of distinct numbers of length (i+1)
that gets ended at digit j
.
We create a grid of shape 2-D array (4x3) where each cell (i, j)
represents the count of distinct number of length (i+1)
. Therefore, each dp[i][j]
will be equal to the sum of all eight dp[i-1][k]
where (k)'s are the numbers that can be reached from
(j)'.
We initialize our dp[][]
table in such a way that dp[0[j]
= 1,
for all j's.
and update our table using the equation mentioned above. And finally ans
will be equal to the sum of dp[N-1][j]
, for all j's
where (j)'s are the reachable from
(i)'.
The time complexity for computing the dp[i][j]
is O(1)
. To compute the final result, the time complexity is O(N)
, hence the total time complexity is O(N)
.
Java Solution
1
2java
3class Solution {
4 // the numbers that can be reached from i
5 private final int[][] moves = new int[][]{{4,6},{6,8},{7,9},{4,8},
6 {0,3,9},{},{1,7,0},{2,6},
7 {1,3},{2,4}};
8
9 private static final int MOD = 1_000_000_007;
10
11 public int knightDialer(int N) {
12 int[][] dp = new int[N][10];
13 // Initialize dp array
14 Arrays.fill(dp[0], 1);
15 for(int i = 1;i<N;++i){
16 // find count for each digit
17 for(int j = 0;j<10;++j){
18 for(int prev:moves[j]){
19 dp[i][j] += dp[i-1][prev];
20 dp[i][j] %= MOD;
21 }
22 }
23 }
24 // Find total count
25 long ans = 0;
26 for(int x:dp[N-1]){
27 ans += x;
28 }
29 ans %= MOD;
30 // return total count
31 return (int)ans;
32 }
33}
The Java solution involves using multi-dimensional arrays and nested loops for finding the total distinct numbers. We use int [][] moves
for storing each distinct number that can be dialed by the knight. After initializing, we compute dp[i][j]
โ total count of distinct numbers of length (i+1)
that gets ended at digit j
. Finally, we add the total count of distinct numbers and return the total distinct count modulo 1_000_000_007
.Python Solution
1 2python 3MOD = 10**9 + 7 4 5# the numbers that can be reached from i 6moves = [[4,6],[6,8],[7,9],[4,8],[0,3,9],[],[1,7,0],[2,6],[1,3],[2,4]] 7 8def knightDialer(N): 9 # Initialize dp array 10 dp = [1] * 10 11 for _ in range(N-1): 12 temp_dp = [0] * 10 13 for i in range(10): 14 for j in moves[i]: 15 temp_dp[j] += dp[i] 16 temp_dp[j] %= MOD 17 dp = temp_dp 18 # return total count 19 return sum(dp) % MOD
The Python solution is similar to the Java solution, but we use a list instead of an array to store each distinct number that can be dialed by the knight. After initializing, we compute dp[i]
using a temporary list temp_dp
- total count of distinct numbers that get ended at the digit i
. We iterate N-1
times to find all distinct numbers of length N
that gets ended at digit i
. Finally, we return the sum of dp
modulo 10^9 + 7
.
Javascript Solution
1 2javascript 3let knightDialer = function(N) { 4 let MOD = 1e9 + 7; 5 6 // the numbers that can be reached from i 7 let moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[0,7,1],[6,2],[1,3],[2,4]]; 8 9 // Initialize dp array 10 let dp = new Array(10).fill(1); 11 for(let _ = 1; _ < N; _++){ 12 let dpNew = new Array(10).fill(0); 13 for(let node = 0; node < 10; node++){ 14 for(let move of moves[node]){ 15 dpNew[move] += dp[node]; 16 dpNew[move] %= MOD; 17 } 18 } 19 dp = dpNew; 20 } 21 // return total count 22 return dp.reduce( (a,b) => a+b ) % MOD; 23}
The Javascript solution also uses arrays to store each distinct number that can be dialed by the knight. We also use a range-based loop to compute dp[i]
, but instead of creating a new array temp_dp
, we utilize dpNew
to find out the count of distinct numbers. Finally, we use the reduce
method to sum up the counts and return the total count modulo 1e9 + 7
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.