Skip to main content

935. Knight Dialer

medium

Count distinct n-digit numbers a chess knight can dial on a phone keypad. 2D DP keyed on (steps-left, current key) — classic transition table with the keypad's adjacency baked in.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell). Given an 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 initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps. As the answer may be very large, return the answer modulo 10^9 + 7.

Constraints

  • 1 <= n <= 5000

Examples

Example 1

Input
n = 1
Output
10

Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2

Input
n = 2
Output
20

Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94].

Example 3

Input
n = 3131
Output
136006598

Explanation: Please take care of the mod.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Precompute the adjacency for each numeric key: 1 -> {6, 8}, 2 -> {7, 9}, 3 -> {4, 8}, etc.

Hint 2

dp[step][key] = number of length-(step+1) sequences ending at key. Recurrence: dp[step][key] = sum of dp[step-1][neighbor] for every neighbor of key.

Hint 3

Base: dp[0][key] = 1 for every numeric key.

Hint 4

Apply mod after each addition. Space optimization: keep only the previous step's row — 10 entries.

Solution approach

Reveal approach

Precompute the knight-jump adjacency for every numeric key on the keypad (1-9 and 0). Maintain a length-10 array dp where dp[k] is the number of valid sequences of the current length ending at key k. Initialize dp[k] = 1 for every key (the length-1 base case). Repeat n-1 times: build a new array next where next[k] = sum of dp[neighbor] for every neighbor of k, taken mod 10^9 + 7. Replace dp with next. After n-1 iterations, the answer is the sum of dp[k] over all 10 keys, mod 10^9 + 7. The transition is a fixed sparse matrix-vector product; for very large n you can apply matrix exponentiation to push the time below O(n).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Apple
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Knight Dialer and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →