Strobogrammatic Number II - Video Solutions

Problem Overview: Generate all numbers of length n that look the same when rotated 180 degrees. Valid strobogrammatic pairs are (0,0), (1,1), (6,9), (8,8), and (9,6). The challenge is building every valid combination while avoiding leading zeros for multi-digit numbers.

Approach 1: Generate All Numbers + Validate (Brute Force) (Time: O(10^n * n), Space: O(n))

The most direct approach generates every possible n-digit number and checks if it remains the same after a 180-degree rotation. Validation works by scanning digits from both ends and confirming each pair matches a valid strobogrammatic mapping. This approach requires iterating through 10^n candidates and performing a two-pointer check of length n. The algorithm is simple but extremely inefficient for larger n. It mainly helps you understand the mapping rules between digits before optimizing the generation process.

Approach 2: Recursive Construction with Symmetric Pairs (Time: O(5^(n/2)), Space: O(5^(n/2)))

A better strategy constructs numbers from the center outward using recursion. Instead of checking every number, build only valid combinations by inserting strobogrammatic digit pairs at the left and right ends. The recursion generates results for length n-2, then wraps each string with the valid pairs. Special handling is required for the middle position when n is odd; only 0, 1, and 8 can appear there. Leading zeros are avoided by skipping the pair (0,0) when filling the outermost level. This technique dramatically reduces the search space because every constructed number is guaranteed to be valid. It’s a classic use of recursion and symmetric string construction.

Approach 3: Iterative BFS Construction (Time: O(5^(n/2)), Space: O(5^(n/2)))

The same idea can be implemented iteratively using a queue. Start with base strings ("" for even lengths or "0", "1", "8" for odd lengths). At each step, insert valid digit pairs around every current string until the length reaches n. The queue naturally expands level by level, similar to breadth‑first search. The complexity matches the recursive approach, but some engineers prefer this version because it avoids recursion depth and makes the construction process explicit. The result set can be stored in an array or list while manipulating digits as a string.

Recommended for interviews: Recursive symmetric construction is the expected solution. It shows you recognize that strobogrammatic numbers are built from mirrored digit pairs and that brute force is unnecessary. Interviewers typically want to see the recursive reduction from n to n-2, handling the odd-length middle case, and avoiding leading zeros. The brute force approach demonstrates understanding of the rotation rule, but the recursive generation shows stronger algorithmic reasoning.