Mobile Numeric Keypad Problem

The problem, simply

An old phone has a keypad with four rows: 1 2 3, 4 5 6, 7 8 9, and * 0 #. You must press exactly n keys. The first press can be any digit. After that, every press must be the same key again, or a key right next to it: up, down, left or right. Never sideways at a slant. The * and # keys are not allowed.

Give back how many different numbers of length n you can type.

A story to remember it

Picture it

Some keys and the keys you may press after them (the key itself included):

• 0 can go to 0 or 8, so 2 choices.
• 1 can go to 1, 2 or 4, so 3 choices.
• 2 can go to 2, 1, 3 or 5, so 4 choices.
• 5 can go to 5, 2, 4, 6 or 8, so 5 choices.
• 8 can go to 8, 5, 7, 9 or 0, so 5 choices.

Examples

Way 1: the simple way

Ask a helper: "starting on this key, with this many presses left, how many numbers can I make?"

1. If only 1 press is left, the answer is 1. You press the key you are on and stop.
2. Otherwise, try every next key (the key itself and its touching keys) and add up what the helper says for each one with one press fewer.
3. Do this for all ten starting keys and add the answers.

class Solution {
    // For each key: the keys you may press next, the key itself first
    int[][] next = {
        {0, 8},          // 0
        {1, 2, 4},       // 1
        {2, 1, 3, 5},    // 2
        {3, 2, 6},       // 3
        {4, 1, 5, 7},    // 4
        {5, 2, 4, 6, 8}, // 5
        {6, 3, 5, 9},    // 6
        {7, 4, 8},       // 7
        {8, 5, 7, 9, 0}, // 8
        {9, 6, 8}        // 9
    };

    public long getCount(int n) {
        if (n <= 0) return 0;
        long total = 0;
        for (int key = 0; key <= 9; key++) {
            total += count(key, n);
        }
        return total;
    }

    private long count(int key, int left) {
        if (left == 1) return 1;             // press this key and stop
        long ways = 0;
        for (int k : next[key]) {
            ways += count(k, left - 1);      // try every next key
        }
        return ways;
    }
}

How long it takes: each call can branch into up to 5 calls, and the calls go n levels deep, so about O(5^n). Extra room: the helpers waiting on each other, O(n).

Way 2: the clever way

The answer for (key, presses) only depends on the answers for (neighbor keys, presses minus 1). So fill a table one row at a time, like the frog numbers on the stones.

1. Row for 1 press: every key gets 1.
2. Row for p presses: for each key, add the numbers in the row above under that key and its touching keys.
3. The answer is the sum of the last row.

You only ever look at the row right above, so two rows of ten numbers are enough.

class Solution {
    public long getCount(int n) {
        if (n <= 0) return 0;
        int[][] next = {
            {0, 8}, {1, 2, 4}, {2, 1, 3, 5}, {3, 2, 6}, {4, 1, 5, 7},
            {5, 2, 4, 6, 8}, {6, 3, 5, 9}, {7, 4, 8}, {8, 5, 7, 9, 0}, {9, 6, 8}
        };
        long[] row = new long[10];
        Arrays.fill(row, 1);                      // 1 press: one number per key
        for (int p = 2; p <= n; p++) {
            long[] newRow = new long[10];
            for (int key = 0; key <= 9; key++) {
                for (int k : next[key]) {
                    newRow[key] += row[k];        // borrow from the row above
                }
            }
            row = newRow;
        }
        long total = 0;
        for (long ways : row) total += ways;
        return total;
    }
}

How long it takes: each new row costs at most 10 keys times 5 neighbors, a fixed amount, so O(n) overall. Extra room: two rows of 10 numbers, O(1).

Watch out for

• Slanted moves are not allowed. 5 does not touch 1, 3, 7 or 9.
• Key 0 only touches 8, because * and # are banned.
• The numbers grow like 5^n in the worst case. Use long, or take the answer modulo a big prime if the problem asks.
• Be clear about n = 0. Most judges expect 0.

What interviewers ask next

• Can you go faster than O(n) for huge n? Yes. One row step is multiplying by a fixed 10 by 10 table of 0s and 1s. Raise that table to the power n - 1 with repeated squaring and the work becomes O(log n).
• What if the keys can also move like a chess knight? Same table filling, only the neighbor lists change. That is the famous "knight dialer" question.
• What if some digits are banned as the first press? Start the first row with 0 under those keys.
• Can you print all the numbers? Only for tiny n, since there can be about 5^n of them. Use backtracking for that.

Remember this

Grown-up words: the stones are the keypad graph, the frog numbers are a dynamic programming table dp[presses][key], keeping only the last row is space optimization, and the fast power trick is matrix exponentiation.