935. Knight Dialer

[sophryu99]

935. Knight Dialer

https://leetcode.com/problems/knight-dialer/description/

A knight could only move in either 2 horizontal + 1 vertical or 2 vertical + 1 horizontal. Graph traversal, DP problem with N stops

1. From a dial pad, store all the possible paths from a number in a dict data structure.
2. For every iteration of jump (i in range(n)), create a next array of [0] * 10 where next[i] = count of dial pad that can be reached from dial pad i

First iteration

0 [2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [2, 2, 0, 0, 0, 0, 0, 0, 0, 0]
2 [2, 2, 2, 0, 0, 0, 0, 0, 0, 0]
3 [2, 2, 2, 2, 0, 0, 0, 0, 0, 0]
4 [2, 2, 2, 2, 3, 0, 0, 0, 0, 0]
5 [2, 2, 2, 2, 3, 0, 0, 0, 0, 0]
6 [2, 2, 2, 2, 3, 0, 3, 0, 0, 0]
7 [2, 2, 2, 2, 3, 0, 3, 2, 0, 0]
8 [2, 2, 2, 2, 3, 0, 3, 2, 2, 0]
9 [2, 2, 2, 2, 3, 0, 3, 2, 2, 2]

3. Update the dp array, and continue with the next iteration

class Solution:
    def knightDialer(self, n: int) -> int:
        dct = {
            0:(4,6),
            1:(6,8),
            2:(7,9),
            3:(4,8),
            4:(0,3,9),
            5:(),
            6:(0,1,7),
            7:(2,6),
            8:(1,3),
            9:(2,4)
        }

        num_keys = 10
        dp = [1] * num_keys # dp[i] = number of times the knight can reach dial pad i

        for _ in range(n - 1):
            nxt = [0] * num_keys
            for i in dct:
                for j in dct[i]:
                    nxt[i] += dp[j]

            dp = nxt

        return sum(dp) % (10**9 + 7)

N: input size N

• Time Complexity: O(N * number of dials in dial pad(10) * max size of dict[i] (3) ) -> O(N)
• Space Complexity: O(1) with dp array of size 10