Strobogrammatic Number II solution and explanation
Google
9 more videos on this problem
LeetCode 247. Strobogrammatic Number II Explanation and Solutionhappygirlzt · 6:31 · 8K views
247. Strobogrammatic Number II | English | MediumSimple Code - 단순코드 · 7:43 · 3K views
Facebook Coding Interview Question | Leetcode 247 | Strobogrammatic Number IIWorkWithGoogler · 21:47 · 2K views
Leetcode 247. Strobogrammatic Number IIAlgorithms Casts · 24:08 · 1K views
Strobogrammitic Number II | Leetcode #247Surjit Singh · 9:38 · 849 views
LeetCode 247. Strobogrammatic Number II | JavaScript & AlgorithmJSer · 21:49 · 769 views
Leetcode 247. Strobogrammatic Number II (backtracking)LetsCode · 9:56 · 439 views
Strobogrammatic Number IIHoaVuCS · 33:36 · 41 views
247. Strobogrammatic Number II | Korean | MediumSimple Code - 단순코드 · 10:13 · 37 views
LeetCode 247: Strobogrammatic Number IIAlitaCode · 27:35 · 33 views
The 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).
Example 1:
Input: n = 2 Output: ["11","69","88","96"]
Example 2:
Input: n = 1 Output: ["0","1","8"]
Constraints:
1 <= n <= 14
Approach overview
Problem Overview: Generate all strobogrammatic numbers of length n. A number is strobogrammatic if it looks the same when rotated 180 degrees. Valid digit pairs are (0,0), (1,1), (6,9), (8,8), and (9,6). The result must include every valid number of length n without leading zeros (except when n = 1).
Approach 1: Brute Force Generation + Validation (O(10^n * n) time, O(n) space)
The most direct idea is to generate every possible n-digit number and check whether it remains valid after a 180-degree rotation. For each candidate, iterate through the digits from both ends and verify the rotation mapping: 0→0, 1→1, 6→9, 8→8, 9→6. Any digit outside this set immediately invalidates the number. This approach performs up to 10^n checks and each validation takes O(n) time, making it extremely slow even for moderate values of n. It demonstrates the property of strobogrammatic numbers but is not practical for interviews.
Approach 2: Recursive Pair Construction (O(5^(n/2)) time, O(5^(n/2)) space)
The efficient approach builds numbers from the center outward using valid strobogrammatic digit pairs. Instead of generating every number, you only place digits that remain valid after rotation. Use recursion to construct smaller strobogrammatic strings of length n-2, then wrap them with valid pairs like "1" + middle + "1" or "6" + middle + "9". The base cases are length 0 (return an empty string) and length 1 (return 0, 1, 8). Avoid placing 0 at the outermost level to prevent leading zeros.
Each recursion level adds symmetric pairs around the inner string. Since there are at most five valid pairs and the recursion depth is roughly n/2, the total number of generated combinations is about 5^(n/2). This directly generates only valid numbers, which is far more efficient than filtering invalid candidates.
The algorithm works naturally with recursion because each valid number can be decomposed into an inner strobogrammatic string plus a symmetric outer pair. The result set is stored using simple string construction, and iteration over candidate pairs is straightforward.
Recommended for interviews: Recursive pair construction is the expected solution. It shows that you recognized the symmetry property of strobogrammatic numbers and avoided brute force enumeration. Mentioning the brute force idea first shows understanding of the problem space, but implementing the recursive construction demonstrates stronger algorithmic thinking.
Solution
If the length is 1, then the strobogrammatic numbers are only 0, 1, 8; if the length is 2, then the strobogrammatic numbers are only 11, 69, 88, 96.
We design a recursive function dfs(u), which returns the strobogrammatic numbers of length u. The answer is dfs(n).
If u is 0, return a list containing an empty string, i.e., [""]; if u is 1, return the list ["0", "1", "8"].
If u is greater than 1, we traverse all the strobogrammatic numbers of length u - 2. For each strobogrammatic number v, we add 1, 8, 6, 9 to both sides of it, and we can get the strobogrammatic numbers of length u.
Note that if u neq n, we can also add 0 to both sides of the strobogrammatic number.
Finally, we return all the strobogrammatic numbers of length n.
The time complexity is O(2^{n+2}).
Similar problems:
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
def dfs(u):
if u == 0:
return ['']
if u == 1:
return ['0', '1', '8']
ans = []
for v in dfs(u - 2):
for l, r in ('11', '88', '69', '96'):
ans.append(l + v + r)
if u != n:
ans.append('0' + v + '0')
return ans
return dfs(n)class Solution {
private static final int[][] PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
private int n;
public List<String> findStrobogrammatic(int n) {
this.n = n;
return dfs(n);
}
private List<String> dfs(int u) {
if (u == 0) {
return Collections.singletonList("");
}
if (u == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> ans = new ArrayList<>();
for (String v : dfs(u - 2)) {
for (var p : PAIRS) {
ans.add(p[0] + v + p[1]);
}
if (u != n) {
ans.add(0 + v + 0);
}
}
return ans;
}
}class Solution {
public:
const vector<pair<char, char>> pairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
vector<string> findStrobogrammatic(int n) {
function<vector<string>(int)> dfs = [&](int u) {
if (u == 0) return vector<string>{""};
if (u == 1) return vector<string>{"0", "1", "8"};
vector<string> ans;
for (auto& v : dfs(u - 2)) {
for (auto& [l, r] : pairs) ans.push_back(l + v + r);
if (u != n) ans.push_back('0' + v + '0');
}
return ans;
};
return dfs(n);
}
};func findStrobogrammatic(n int) []string {
var dfs func(int) []string
dfs = func(u int) []string {
if u == 0 {
return []string{""}
}
if u == 1 {
return []string{"0", "1", "8"}
}
var ans []string
pairs := [][]string{{"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"}}
for _, v := range dfs(u - 2) {
for _, p := range pairs {
ans = append(ans, p[0]+v+p[1])
}
if u != n {
ans = append(ans, "0"+v+"0")
}
}
return ans
}
return dfs(n)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Generation + Validation | O(10^n * n) | O(n) | Conceptual baseline to understand strobogrammatic validation |
| Recursive Pair Construction | O(5^(n/2)) | O(5^(n/2)) | Generating all valid numbers efficiently using symmetry |
Frequently asked questions
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.