Mobile Numeric Keypad

There is a standard numeric keypad on a mobile phone. You can only press the current button or buttons that are directly up, left, right, or down from it (for ex if you press 5, then pressing 2, 4, 6 & 8 are allowed). Diagonal movements and pressing the bottom row corner buttons (* and #) are prohibited.

Given a number n, find the number of possible unique sequences of length n that you can create by pressing buttons. You can start from any digit.

Examples

Input: n = 1
Output:  10
Explanation: Number of possible numbers are 10 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

Input:  n = 2
Output:  36
Explanation:  Possible numbers: 00, 08, 11, 12, 14, 22, 21, 23, 25 and so on. If we start with 0, valid numbers will be 00, 08 (count: 2). If we start with 1, valid numbers will be 11, 12, 14 (count: 3). If we start with 2, valid numbers  will be 22, 21, 23,25 (count: 4). If we start with 3, valid numbers will be 33, 32, 36 (count: 3). If we start with 4, valid numbers will be 44,41,45,47 (count: 4). If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5) and so on.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ n ≤ 25

Approach 01:

class Solution {
  public:
    long long help(int row, int col, int n, vector<vector<vector<long long>>> &dp) {
        if (row > 3 || col > 2 || row < 0 || col < 0) return 0;
        if (row == 3 && (col == 0 || col == 2)) return 0;
        if (n == 1) return 1;
        if (dp[row][col][n] != -1) return dp[row][col][n];
        n--;
        return dp[row][col][n + 1] = help(row - 1, col, n, dp) + help(row, col - 1, n, dp) +
                                     help(row + 1, col, n, dp) + help(row, col + 1, n, dp) + 
                                     help(row, col, n, dp);
    }

    long long getCount(int n) {
        long long total_count = 0;
        vector<vector<vector<long long>>> dp(4, vector<vector<long long>>(3, vector<long long>(n + 1, -1)));
        for (int row = 0; row < 4; row++) {
            for (int col = 0; col < 3; col++) {
                if (row == 3 && (col == 0 || col == 2)) continue;
                total_count += help(row, col, n, dp);
            }
        }
        return total_count;
    }
};

class Solution:
    def help(self, row, col, n, dp):
        if row > 3 or col > 2 or row < 0 or col < 0:
            return 0
        if row == 3 and (col == 0 or col == 2):
            return 0
        if n == 1:
            return 1
        if dp[row][col][n] != -1:
            return dp[row][col][n]
        n -= 1
        dp[row][col][n + 1] = self.help(row - 1, col, n, dp) + self.help(row, col - 1, n, dp) + \
                              self.help(row + 1, col, n, dp) + self.help(row, col + 1, n, dp) + \
                              self.help(row, col, n, dp)
        return dp[row][col][n + 1]

    def getCount(self, n):
        total_count = 0
        dp = [[[-1 for _ in range(n + 1)] for _ in range(3)] for _ in range(4)]
        for row in range(4):
            for col in range(3):
                if row == 3 and (col == 0 or col == 2):
                    continue
                total_count += self.help(row, col, n, dp)
        return total_count

Initialization:

• The function getCount(int n) initializes the total count of possible sequences to 0.
• A 3D vector dp of dimensions 4x3x(n+1) is created and initialized to -1. This vector will be used for memoization to store results of subproblems to avoid redundant calculations.

Base Cases in help Function:

• The function help(int row, int col, int n, vector<vector<vector<long long>>> &dp) handles the recursive calculation of possible sequences.
• If the current position (row, col) is out of bounds of the keypad, it returns 0.
• If the current position is one of the invalid keys (e.g., (3, 0) or (3, 2) which correspond to ‘*’ and ‘#’), it returns 0.
• If n (the number of remaining keys to press) is 1, it returns 1 because there’s exactly one way to press one key.

Memoization Check:

• Before performing recursive calculations, the function checks if the result for the current position and remaining n is already computed and stored in dp. If so, it returns that value.

Recursive Calculation:

• The function recursively calls itself for all possible moves (up, down, left, right, and staying on the same key) and sums the results.
• The n is decremented by 1 before making the recursive calls because one key press is accounted for.

Summing Results in getCount Function:

• The getCount function iterates through all keys on the keypad, excluding the invalid keys.
• For each valid key, it calls the help function to calculate the number of valid sequences starting from that key.
• It sums up the results from all valid starting keys to get the total count.

Return the Total Count:

• Finally, the total count of valid sequences is returned.

Time Complexity:

• The time complexity can be approximated by considering the number of states in the memoization table.
• There are 4 rows and 3 columns, and n possible lengths.
• Thus, there are 4 * 3 * n states to be computed.
• Each state computation involves constant time operations (summing up five recursive calls), so the overall time complexity is O(4 * 3 * n), which simplifies to O(12 * n) or O(n).

Space Complexity:

• The space complexity is dominated by the memoization table dp.
• The size of dp is 4 * 3 * (n + 1), which simplifies to O(12 * n) or O(n) for practical purposes.