Strobogrammatic Number II
Medium · Arrays & Hashing · Explanation and code example
Iteration (Level Order Traversal)
How it works
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.
Steps
- Determine the starting point based on parity: if
nis odd, start with["0", "1", "8"]; if even, start with[""]. - Track the current string length, starting at
n % 2. - 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.
- Increment the length by
- Return the final list of strobogrammatic numbers.
Complexity
-
Time complexity:
O(N × 5^{lfloor N/2 rfloor + 1}) -
Space complexity:
O(N × 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
Nis the length of strobogrammatic numbers we need to find.
Things to watch for
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.
Python code example
from typing import List
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
C++ code example
class Solution {
public:
vector<vector<char>> reversiblePairs = {
{'0', '0'}, {'1', '1'},
{'6', '9'}, {'8', '8'}, {'9', '6'}
};
vector<string> findStrobogrammatic(int n) {
queue<string> q;
int currStringsLength;
// When n is even, it means when decreasing by 2 we will go till 0.
if (n % 2 == 0) {
// We will start with 0-digit strobogrammatic numbers.
currStringsLength = 0;
q.push("");
} else {
// We will start with 1-digit strobogrammatic numbers.
currStringsLength = 1;
q.push("0");
q.push("1");
q.push("8");
}
while (currStringsLength < n) {
currStringsLength += 2;
for (int i = q.size(); i > 0; --i) {
string number = q.front();
q.pop();
for (vector<char>& pair : reversiblePairs) {
if (currStringsLength != n || pair[0] != '0') {
q.push(pair[0] + number + pair[1]);
}
}
}
}
vector<string> stroboNums;
while (!q.empty()) {
stroboNums.push_back(q.front());
q.pop();
}
return stroboNums;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.