1. Recursion

Intuition

A strobogrammatic number looks the same when rotated 180 degrees. Only certain digit pairs maintain their appearance after rotation: (0,0), (1,1), (6,9), (8,8), and (9,6). We can build these numbers recursively from the inside out. Start with the base cases: empty string for even length or single symmetric digits (0, 1, 8) for odd length. Then wrap each smaller solution with valid digit pairs. The key insight is that leading zeros are invalid, so we skip adding '0' at the outermost layer.

Algorithm

1. Define the five reversible digit pairs that look the same when rotated 180 degrees.
2. Create a recursive function that builds strobogrammatic numbers of length n:
   • Base case: if n == 0, return an empty string (the center for even-length numbers).
   • Base case: if n == 1, return the three single-digit strobogrammatic numbers: "0", "1", "8".
3. Recursively generate strobogrammatic numbers of length n - 2.
4. For each smaller number, wrap it with each valid digit pair (one digit at the start, its pair at the end).
5. Skip pairs starting with '0' when building the outermost layer (when n equals the final target length) to avoid leading zeros.
6. Return all generated numbers.

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        reversible_pairs = [
            ['0', '0'], ['1', '1'], 
            ['6', '9'], ['8', '8'], ['9', '6']
        ]

        def generate_strobo_numbers(n, final_length):
            if n == 0:
                # 0-digit strobogrammatic number is an empty string.
                return [""]

            if n == 1:
                # 1-digit strobogrammatic numbers.
                return ["0", "1", "8"]

            prev_strobo_nums = generate_strobo_numbers(n - 2, final_length)
            curr_strobo_nums = []

            for prev_strobo_num in prev_strobo_nums:
                for pair in reversible_pairs:
                    if pair[0] != '0' or n != final_length:
                        curr_strobo_nums.append(pair[0] + prev_strobo_num + pair[1])

            return curr_strobo_nums
            
        return generate_strobo_numbers(n, n)

Time & Space Complexity

• Time complexity: $O(N \cdot 5^{\lfloor N/2 \rfloor + 1})$

• Space complexity: $O(N \cdot 5^{\lfloor N/2 \rfloor})$

Where $N$ is the length of strobogrammatic numbers we need to find.

---

2. Iteration (Level Order Traversal)

Intuition

Instead of recursion, we can build strobogrammatic numbers iteratively using a BFS-like approach. Start from the center and expand outward level by level. For odd-length numbers, begin with single digits (0, 1, 8). For even-length numbers, begin with an empty string. Each iteration adds two digits to the current strings, growing them symmetrically until we reach the target length.

Algorithm

1. Determine the starting point based on parity: if n is odd, start with ["0", "1", "8"]; if even, start with [""].
2. Track the current string length, starting at n % 2.
3. While the current length is less than n:
   • Increment the length by 2 (adding one digit to each end).
   • For each existing string, wrap it with each valid digit pair.
   • Skip '0' as the leading digit when at the final length.
4. Return the final list of strobogrammatic numbers.

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        reversible_pairs = [
            ['0', '0'], ['1', '1'], 
            ['6', '9'], ['8', '8'], ['9', '6']
        ]

        # When n is even (n % 2 == 0), we start with strings of length 0 and
        # when n is odd (n % 2 == 1), we start with strings of length 1.
        curr_strings_length = n % 2
        
        q = ["0", "1", "8"] if curr_strings_length == 1 else [""]
        
        while curr_strings_length < n:
            curr_strings_length += 2
            next_level = []
            
            for number in q:
                for pair in reversible_pairs:
                    if curr_strings_length != n or pair[0] != '0':
                        next_level.append(pair[0] + number + pair[1])
            q = next_level
            
        return q

Time & Space Complexity

• Time complexity: $O(N \cdot 5^{\lfloor N/2 \rfloor + 1})$

• Space complexity: $O(N \cdot 5^{\lfloor N/2 \rfloor})$

  • Note: In javascript and python, in the last iteration the arrary, is the output array. Thus it will not be considered in auxiliary space. But still, the overall order of the complexity remains the same.

Where $N$ is the length of strobogrammatic numbers we need to find.

---

Common Pitfalls

Allowing Leading Zeros

Numbers cannot have leading zeros (except for "0" itself when n=1). When building the outermost layer of digits, you must skip the (0, 0) pair to avoid generating invalid numbers like "010" or "00100".

Forgetting That 6 and 9 Map to Each Other

Unlike 0, 1, and 8 which map to themselves when rotated 180 degrees, 6 becomes 9 and 9 becomes 6. The reversible pairs must include both (6, 9) and (9, 6) to correctly generate all strobogrammatic numbers.

Incorrect Base Cases for Odd vs Even Length

For even-length numbers, the recursive base case is an empty string (length 0). For odd-length numbers, the center digit must be strobogrammatic by itself: only 0, 1, or 8. Mixing up these base cases or forgetting the odd-length center constraint will produce incorrect results.