Domain 2MediumMEDIUM

Knight Dialer

LeetCode problem 935: Knight Dialer (medium).

Domain: medium•Updated: 2026-09-04
#Dynamic Programming

Problem Breakdown

We are asked to count how many distinct phone numbers of length n can be dialed using a chess knight on a standard numeric keypad layout (0-9). The knight starts at any valid digit and makes exactly n - 1 jumps. Each jump must land on another valid digit according to the L-shaped movement rules.

  • Inputs: An integer n representing the length of the phone number sequence.
  • Outputs: A single integer representing the total count of distinct sequences, modulo 109+710^9 + 7.
  • Implicit Constraints: The keypad layout is fixed (standard US/UK pad). Key ‘5’ and potentially others have restricted connectivity based on geometry. We must handle large numbers using modular arithmetic to prevent overflow in other languages (though Python handles big ints automatically, the requirement specifies modulo output).
  • Edge Cases:
    • n = 1: The knight makes no jumps; any of the 10 digits is a valid number. Output should be 10.
    • Key ‘5’: On this specific keypad layout (where ‘0’ is centered below row 8), key ‘5’ has no valid outgoing or incoming moves from other keys due to geometry constraints. It acts as an isolated node for n > 1.

Intuition

A brute-force approach would involve generating all possible paths of length n using Depth First Search (DFS). Since the knight typically branches into ~2-3 new positions per step, this grows exponentially (O(3n)O(3^n) or similar), which will time out for N=5000N=5000.

The key insight is that we only care about how many ways to reach each digit at a specific step i, not the exact paths. This transforms the problem into counting walks on a graph.

  1. State: Let dp[i][digit] be the number of valid sequences ending at digit after exactly i jumps (length i+1).
  2. Transition: To find counts for step i, we sum up the ways to reach any neighbor from all digits reachable in one knight move: new_dp[neighbor] += dp[current_digit].
  3. Optimization: Since the graph structure is static, this is a linear recurrence relation over time steps. We can iterate through each jump count from 1 to n-1, updating our counts for all digits simultaneously using two arrays (current and next state).

Approach

  1. Define an adjacency list representing valid knight moves between keys ‘0’-‘9’. Note that key ‘5’ has no neighbors in this specific layout.
  2. Initialize a DP array of size 10 with 1 for each digit, representing the count of sequences starting at that digit (length 1).
  3. Iterate from step 1 to n-1. In each iteration:
    • Create a new temporary DP array initialized to zeros.
    • For every key in our current state, add its count to all reachable neighbors’ counts in the next state.
    • Apply modulo 109+710^9 + 7 at each addition to keep numbers manageable and correct per requirements.
  4. After n-1 iterations (representing length n), sum up the values in the DP array. This total represents all valid sequences ending on any digit.

Complexity Analysis

  • Time Complexity: O(N)O(N). We perform a constant number of operations per step (iterating over 10 digits and their neighbors). Since there are only 10 keys, each iteration takes O(1)O(1) effectively relative to N. Total time is proportional to the input size.
  • Space Complexity: O(1)O(1). We use fixed-size arrays for DP states (size 10) regardless of how large n gets.

Solution

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # Define the adjacency list based on valid knight moves 
        # for a standard phone pad layout (where '5' is isolated).
        adj = {
            "0": ["4", "6"],
            "1": ["6", "8"],
            "2": ["7", "9"],
            "3": ["4", "8"],
            "4": ["0", "3", "9"],
            # Key '5' has no valid moves on this specific pad layout.
            "5": [], 
            "6": ["1", "7", "0"],
            "7": ["2", "6"],
            "8": ["1", "3", "9"],
            "9": ["4", "2"]
        }

        # dp[i] stores the number of ways to end at digit i.
        # Initialize with 1 for each key, representing valid starting positions (length 1).
        dp = [1] * 10
        
        # Perform n - 1 jumps
        for _ in range(n - 1):
            new_dp = [0] * 10
            
            # Iterate over all digits to propagate counts to neighbors
            for digit, count in enumerate(dp):
                if count == 0: 
                    continue
                
                current_digit_str = str(digit)
                
                # Distribute the ways from this digit to its valid moves
                for neighbor in adj[current_digit_str]:
                    new_dp[int(neighbor)] += count
            
            dp = [(x % MOD) for x in new_dp]

        return sum(dp) % MOD

Edge Cases Handled

  • n=1: The loop range(n-1) executes 0 times. We simply return the initial sum of [1]*10, which is 10, matching Example 1.
  • Large n (5000): Python handles large integers automatically during intermediate steps; modulo arithmetic ensures we meet output constraints and prevent memory bloat in languages with fixed-size ints.
  • Isolated Key ‘5’: The adjacency list explicitly sets adj["5"] to an empty list, ensuring that any path landing on or starting at 5 (for n > 1) does not propagate further counts, correctly reflecting the geometry of the keypad where no knight move lands on/off key 5.
  • Modulo Arithmetic: The modulo operation is applied after every addition and before returning to ensure the result fits within standard integer limits for other languages and matches LeetCode requirements exactly.