Strobogrammatic Number II - Practice Coding Problems

Strobogrammatic Number II - Problem

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

The valid strobogrammatic digits are: 0, 1, 6, 8, 9 where:

0 rotates to 0
1 rotates to 1
6 rotates to 9
8 rotates to 8
9 rotates to 6

Input & Output

Example 1 — Small Case

$ Input: n = 2

› Output: ["11","69","88","96"]

💡 Note: All 2-digit strobogrammatic numbers: 11 (1↔1), 69 (6↔9), 88 (8↔8), 96 (9↔6)

Example 2 — Single Digit

$ Input: n = 1

› Output: ["0","1","8"]

💡 Note: Single digits that look the same upside down: 0, 1, and 8

Example 3 — Larger Case

$ Input: n = 4

› Output: ["1001","1111","1691","1881","1961","6009","6119","6699","6889","6969","8008","8118","8698","8888","8968","9006","9116","9696","9886","9966"]

💡 Note: 4-digit numbers built by adding valid pairs around 2-digit strobogrammatic numbers, excluding those with leading zeros

Constraints

0 ≤ n ≤ 14

Visualization

Tap to expand

Understanding the Visualization

Input

Length n = 2

Valid Digits

Use pairs: 0↔0, 1↔1, 6↔9, 8↔8, 9↔6

Output

All valid 2-digit strobogrammatic numbers

Key Takeaway

🎯 Key Insight: Build strobogrammatic numbers recursively by placing valid digit pairs symmetrically from outside to inside

Asked in

G Google 30 f Facebook 25 a Amazon 20

The key insight is to build strobogrammatic numbers recursively by placing valid digit pairs symmetrically. The optimal approach uses recursive construction to generate numbers from outside-in, ensuring all results are valid. Time: O(5^(n/2)), Space: O(n × 5^(n/2))

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(5^(n/2))	O(n × 5^(n/2))	Use memoization to cache recursive results and avoid recomputation
Brute Force Generation	O(10ⁿ)	O(k)	Generate all possible n-digit numbers and filter strobogrammatic ones
Recursive Construction	O(5^(n/2))	O(n × 5^(n/2))	Build strobogrammatic numbers recursively from outside to inside

Memoized Recursion — Algorithm Steps

Create memoization cache
Check cache before computing
Store and return computed results

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look up if result already computed

Compute

Calculate if not cached

Store

Cache result for future use

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 20

typedef struct {
    char** strings;
    int size;
    int computed;
} MemoEntry;

MemoEntry memo[MAX_N];

char** helper(int m, int* returnSize) {
    if (memo[m].computed) {
        *returnSize = memo[m].size;
        char** result = (char**)malloc(memo[m].size * sizeof(char*));
        for (int i = 0; i < memo[m].size; i++) {
            result[i] = (char*)malloc(strlen(memo[m].strings[i]) + 1);
            strcpy(result[i], memo[m].strings[i]);
        }
        return result;
    }
    
    char** result;
    if (m == 0) {
        result = (char**)malloc(1 * sizeof(char*));
        result[0] = (char*)malloc(1 * sizeof(char));
        result[0][0] = '\0';
        *returnSize = 1;
    } else if (m == 1) {
        result = (char**)malloc(3 * sizeof(char*));
        result[0] = (char*)malloc(2 * sizeof(char));
        result[1] = (char*)malloc(2 * sizeof(char));
        result[2] = (char*)malloc(2 * sizeof(char));
        strcpy(result[0], "0");
        strcpy(result[1], "1");
        strcpy(result[2], "8");
        *returnSize = 3;
    } else {
        int prevSize;
        char** prev = helper(m - 2, &prevSize);
        
        result = (char**)malloc(prevSize * 5 * sizeof(char*));
        *returnSize = 0;
        
        for (int i = 0; i < prevSize; i++) {
            char pairs[5][3] = {"00", "11", "69", "88", "96"};
            for (int j = 0; j < 5; j++) {
                result[*returnSize] = (char*)malloc((m + 1) * sizeof(char));
                sprintf(result[*returnSize], "%c%s%c", pairs[j][0], prev[i], pairs[j][1]);
                (*returnSize)++;
            }
        }
        
        for (int i = 0; i < prevSize; i++) {
            free(prev[i]);
        }
        free(prev);
    }
    
    // Store in memo
    memo[m].strings = (char**)malloc(*returnSize * sizeof(char*));
    memo[m].size = *returnSize;
    memo[m].computed = 1;
    for (int i = 0; i < *returnSize; i++) {
        memo[m].strings[i] = (char*)malloc(strlen(result[i]) + 1);
        strcpy(memo[m].strings[i], result[i]);
    }
    
    return result;
}

char** solution(int n, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    char** result = helper(n, returnSize);
    
    // Remove numbers with leading zeros (except "0" itself when n=1)
    if (n > 1) {
        int newSize = 0;
        for (int i = 0; i < *returnSize; i++) {
            if (result[i][0] != '0') {
                result[newSize++] = result[i];
            } else {
                free(result[i]);
            }
        }
        *returnSize = newSize;
    }
    
    return result;
}

int main() {
    // Initialize memo
    for (int i = 0; i < MAX_N; i++) {
        memo[i].computed = 0;
    }
    
    int n;
    scanf("%d", &n);
    
    int returnSize;
    char** result = solution(n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(5^(n/2))

Same as recursive approach, but cached for repeated calls

✓ Linear Growth

Space Complexity

O(n × 5^(n/2))

Cache storage plus recursion stack and result strings

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler