Mobile Numeric Keypad Problem [IMP]

Problem Statement

Given a mobile numeric keypad (like an old phone), count the number of possible numeric sequences of length n starting from any key. From a key, you can only press the same key or move to an adjacent key (up, down, left, right). The * and # keys are not allowed.

The keypad layout:

Example:

• Input: n = 1

• Output: 10

• Explanation: Each single digit (0-9) is a valid sequence.

• Input: n = 2

• Output: 36

• Explanation: From each key, you can press itself or adjacent keys. Total valid 2-digit sequences = 36.

Noob-Friendly Explanation

Remember those old Nokia phones with physical buttons? Imagine you can only press buttons that are next to your current button (up, down, left, right) or press the same button again. You need to press exactly n buttons total. How many different number sequences can you type?

For example, if you start at 5, you can go to 2, 4, 6, 8, or stay at 5. Each of those has their own neighbors for the next press, and so on.

Approach 1: Brute Force (Recursion)

Intuition

From each starting key, recursively explore all possible next keys (adjacent + same). Count all valid sequences of length n.

Algorithm

1. Define the adjacency for each key on the keypad.
2. For each starting key (0-9), recursively generate sequences of length n.
3. Sum up all valid sequences.

class Solution {
    // Adjacency list: for each key, list of keys reachable (including itself)
    int[][] adjacent = {
        {0, 8},          // 0: can go to 0, 8
        {1, 2, 4},       // 1: can go to 1, 2, 4
        {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 int countSequences(int n) {
        int total = 0;
        for (int key = 0; key <= 9; key++) {
            total += solve(key, n);
        }
        return total;
    }

    private int solve(int currentKey, int remaining) {
        if (remaining == 1) return 1;

        int count = 0;
        for (int nextKey : adjacent[currentKey]) {
            count += solve(nextKey, remaining - 1);
        }
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(5^n) - Each key has at most 5 neighbors, and we explore n levels deep.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming)

Intuition

Use a DP approach where we track the count of sequences of length i ending at each key. For each step, the count for a key is the sum of counts of all its neighbors (including itself) from the previous step.

Algorithm

1. Create dp[10] where dp[key] = number of sequences of current length ending at key. Initially all 1 (length 1).
2. For each length from 2 to n, update dp using the adjacency list.
3. The answer is the sum of all dp[key] values after n steps.

class Solution {
    public int countSequences(int n) {
        int[][] adjacent = {
            {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
        };

        // dp[key] = number of sequences of current length ending at key
        long[] dp = new long[10];
        // Base case: sequences of length 1
        for (int i = 0; i <= 9; i++) {
            dp[i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            long[] newDp = new long[10];
            for (int key = 0; key <= 9; key++) {
                for (int neighbor : adjacent[key]) {
                    newDp[key] += dp[neighbor];
                }
            }
            dp = newDp;
        }

        long total = 0;
        for (int key = 0; key <= 9; key++) {
            total += dp[key];
        }
        return (int) total;
    }
}

Complexity Analysis

• Time Complexity: O(n) - For each length we do O(10 × 5) = O(1) work per step, so total is O(n).
• Space Complexity: O(1) - We use two arrays of fixed size 10.