We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Knight Dialer

Difficulty: Medium

Problem Description

Given a chess knight and a phone pad, the knight can only stand on numeric cells and can jump in a unique "L" shape. Given an integer n, return how many distinct phone numbers of length n can be dialed using valid knight jumps.

Key Insights

  • The knight can move to specific positions on the phone pad based on its unique movement.
  • The problem can be solved using dynamic programming by keeping track of the number of ways to reach each position on the pad at each step.
  • Each position on the pad can be represented as a 2D grid, and the possible moves of the knight can be pre-defined.
  • The result should be computed modulo (10^9 + 7) due to the potential size of numbers involved.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (optimized to use constant space)

Solution

To solve the problem, we can utilize dynamic programming. We maintain a 2D array to represent the number of ways to reach each cell of the phone pad after each jump. The valid knight moves are pre-defined, and for each position, we accumulate the counts from the previous step based on these moves. Finally, we sum up the counts from all positions to get the total distinct phone numbers of length n.

Code Solutions

def knightDialer(n):
    MOD = 10**9 + 7
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), 
             (1, 2), (1, -2), (-1, 2), (-1, -2)]
    pad = [0] * 10
    
    # Initial counts for one digit numbers
    for i in range(10):
        pad[i] = 1
    
    for _ in range(1, n):
        new_pad = [0] * 10
        for i in range(3):
            for j in range(3):
                num = i * 3 + j
                if num > 9: continue
                for move in moves:
                    x, y = i + move[0], j + move[1]
                    if 0 <= x < 3 and 0 <= y < 3:
                        next_num = x * 3 + y
                        if next_num == 10: continue  # Skip 0
                        new_pad[next_num] = (new_pad[next_num] + pad[num]) % MOD
        pad = new_pad
    
    return sum(pad) % MOD
← Back to All Questions