🌱 Keegan's Digital Garden

935. Knight Dialer

4 min read

📝 Problem Details

chess knight movement rules: move two squares vertically and one square horizontally move two squares horizontally and one square vertically input integer n return how many distinct phone numbers of length n we can dial you are allowed to place the knight on any numeric cell all jumps to form a number must be a valid knight move

💭Intuition

We model the problem as a graph traversal using the knight’s movement pattern on a phone keypad.

Phone layout:

    1 2 3
    4 5 6
    7 8 9
      0

From each digit, we can define which digits are reachable using a knight move.  
For example:
- From 1, knight can move to 6 and 8
- From 0, knight can move to 4 and 6

Using this, we construct a map of possible jumps.  
Then, we use dynamic programming to count how many numbers of length `n` can be formed from each starting digit.

We initialize our dp array with dp[0][i] = 1 for all digits i (base case: sequences of length 1).  
We iterate from length 1 to `n - 1`, updating the number of ways to reach each digit using the knight’s move map.

At the end, sum up all dp[n-1][i] for i in 0..9 to get the final result.

💡 Explanation of Solution

observations:

1. subproblem?
At each digit and at each step, the knight has a limited number of places it can jump to.
So a subproblem is: how many sequences of length `k` can be formed starting from digit `d`.

2. top-down vs bottom-up
Either approach works. Top-down requires memoization.
Bottom-up can be optimized using rolling arrays of size 10.

3. state definition
Let dp[k][digit] = number of sequences of length k ending at digit `digit`.

4. recurrence relation
dp[k][digit] = sum of all dp[k - 1][prev_digit] where prev_digit can jump to digit

We’ll use the knight move map to compute which digits can jump to which.

⌛ Complexity Analysis

Time Complexity: O(n * 10) = O(n)
- For each of the n steps, we iterate over all 10 digits and compute transitions.

Space Complexity: O(10)
- We only need to store dp values for the current and previous step, so space can be optimized to O(10).

💻 Implementation of Solution

class Solution {
public:
    int knightDialer(int n) {
        const int MOD = 1e9 + 7;
 
        // Define all possible knight moves from each digit on the keypad
        vector<vector<int>> moves = {
            {4, 6},    // 0 -> can jump to 4 or 6
            {6, 8},    // 1 -> can jump to 6 or 8
            {7, 9},    // 2 -> can jump to 7 or 9
            {4, 8},    // 3 -> can jump to 4 or 8
            {0, 3, 9}, // 4 -> can jump to 0, 3, or 9
            {},        // 5 -> cannot jump anywhere
            {0, 1, 7}, // 6 -> can jump to 0, 1, or 7
            {2, 6},    // 7 -> can jump to 2 or 6
            {1, 3},    // 8 -> can jump to 1 or 3
            {2, 4}     // 9 -> can jump to 2 or 4
        };
 
        // Initialize the base case: for length = 1, we can dial each digit once
        vector<int> prev(10, 1);
 
        // Loop for the remaining n-1 digits
        for(int i=1; i < n; i++) {
            vector<int> curr(10,0); // To store new counts for this round
 
            // For each digit, calculate number of ways to reach it
            for(int digit = 0; digit <= 9; digit++) {
                for(int next : moves[digit]) {
                    // Add the number of ways to reach `next` in the previous step
                    curr[digit] = (curr[digit] + prev[next]) % MOD;
                }
            }
            // Update for the next iteration
            prev = curr;
        }
 
        // Sum all valid ways to end at each digit after n moves
        int result = 0;
        for(int count : prev) {
            result = (result + count) % MOD;
        }
 
        return result;
    }
};

Graph View