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.