Is Strobogrammatic Number II easy or hard?

Strobogrammatic Number II is generally rated Medium difficulty. The challenge is recognizing that the number must be constructed symmetrically using valid rotation pairs rather than brute forcing all numbers.

Strobogrammatic Number II Python/Java solution

Python, Java, C++, and Go implementations typically follow the same recursive pattern. A helper function generates strobogrammatic strings of length n-2 and wraps them with valid pairs such as (1,1), (6,9), and (9,6) while avoiding leading zeros.

How to solve Strobogrammatic Number II in O(n)?

Generating all strobogrammatic numbers cannot be done in O(n) time because the number of valid outputs grows exponentially. The best practical solution constructs numbers recursively using valid rotation pairs, producing around 5^(n/2) combinations.

What is the best approach for Strobogrammatic Number II?

Recursive pair construction is the most efficient approach. Instead of checking every number, the algorithm builds valid strobogrammatic numbers by placing symmetric digit pairs like (1,1), (6,9), and (9,6) around smaller valid strings. This reduces the search space and runs in about O(5^(n/2)) time.

Is Strobogrammatic Number II asked at Google/Amazon/Meta?

Strobogrammatic problems have appeared in interviews at companies like Google, Amazon, and Meta, especially for roles that emphasize recursion and string manipulation. Variants such as Strobogrammatic Number I and III are also common.

What data structure is used in Strobogrammatic Number II?

The solution primarily uses recursion and string construction. A list or array stores intermediate results, while recursion builds numbers from the center outward using valid digit pairs.

What is the time complexity of Strobogrammatic Number II?

The optimal recursive solution runs in O(5^(n/2)) time because each level of recursion can add up to five valid digit pairs and the recursion depth is roughly n/2. Space complexity is also O(5^(n/2)) since all valid numbers of length n must be stored in the result list.

Description Hints 1 Solution Video 6:31

247. Strobogrammatic Number II

Medium53.5% acceptance2 companiesPremium elsewhere, free here

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).

Example 1:

Input: n = 2
Output: ["11","69","88","96"]

Example 2:

Input: n = 1
Output: ["0","1","8"]

Constraints:

1 <= n <= 14

Asked at 2 companies

Topics

Hints open one at a time

Hint 1

Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

6:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution