How do you solve Knight Dialer on LeetCode?

Knight Dialer (LeetCode #935) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The knight's movement creates a unique graph of possible transitions between digits.

What is the brute force solution for Knight Dialer?

The brute force approach for Knight Dialer is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible knight moves from each digit on the keypad for the given number of jumps. This method explores every possible path the knight can take, which can be computationally expensive. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Knight Dialer?

Knight Dialer uses the following concepts: Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Graph Traversal.

What are the interview tips for Knight Dialer?

Clearly explain your thought process and approach before coding. Discuss edge cases, such as n = 1, and how they affect your solution. Practice writing clean, efficient code to avoid unnecessary complexity.

What are common mistakes when solving Knight Dialer?

Not considering the boundaries of the keypad when implementing moves. Failing to apply the modulo operation correctly, leading to overflow.

#935

Knight Dialer

Medium

Dynamic ProgrammingDynamic ProgrammingGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to efficiently calculate the number of distinct phone numbers. Instead of exploring all paths, we build the solution iteratively, storing results of subproblems to avoid redundant calculations.

⚙️

Algorithm

3 steps

1Step 1: Create a 2D array dp where dp[i][j] represents the number of ways to reach digit j in i moves.
2Step 2: Initialize dp[0][j] to 1 for all j (0-9) since there's one way to start at each digit.
3Step 3: For each move from 1 to n-1, update dp[i][j] based on valid knight moves from all digits.

solution.py17 lines

1# Full working Python code
2MOD = 10**9 + 7
3
4def knightDialer(n):
5    moves = [[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9], [1, 7], [0, 1], [2, 4], [1, 3], [2, 4]]
6    if n == 1:
7        return 10
8    dp = [[0] * 10 for _ in range(n)]
9    for i in range(10):
10        dp[0][i] = 1
11    for i in range(1, n):
12        for j in range(10):
13            for move in moves[j]:
14                dp[i][move] = (dp[i][move] + dp[i-1][j]) % MOD
15    return sum(dp[n-1]) % MOD
16
17print(knightDialer(2))

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the number of moves (n) and the 10 digits. The space complexity is O(n) due to the dp array storing results for each move.

1The knight's movement creates a unique graph of possible transitions between digits.
2Dynamic programming allows us to build solutions incrementally, reducing redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.