#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/leetcode-935-knight-dialer-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/leetcode-935-knight-dialer-implementation

Repovive

LeetCode 935 Knight Dialer - Implementation - Coding Patterns II: Trees, Graphs & Dynamic Programming | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 935 Knight Dialer - Implementation

The code

Use $2$ arrays to track counts at the current and previous hops. Sum all digits at the end.

function knightDialer(n):
    MOD = 10^9 + 7
    moves = {
        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]
    }
    prev = [1] * 10
    for hop in range(1, n):
        curr = [0] * 10
        for digit in range(10):
            for src in moves[digit]:
                curr[digit] = (curr[digit] + prev[src]) % MOD
        prev = curr
    return sum(prev) % MOD

$O(n)$ time, $O(1)$ space (fixed-size arrays).