Strobogrammatic Number III solution and explanation
4 more videos on this problem
LeetCode 248. Strobogrammatic Number IIIHappy Coding · 19:26 · 1K views
Leetcode 248 strobogrammatic number IIIZhenyu Yang · 25:37 · 1K views
248. Strobogrammatic Number III (Leetcode Hard)Programming Live with Larry · 39:46 · 309 views
LeetCode248 Strobogrammatic Number III【Java/Python/C++】(1-600三种语言视频讲解加微信flageek996网址flageek996.com）FLAGeek官方频道 · 2:02 · 180 views
LeetCode 248: Strobogrammatic Number IIIAlitaCode · 29:48 · 3 views
The problem
Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high].
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: low = "50", high = "100" Output: 3
Example 2:
Input: low = "0", high = "0" Output: 1
Constraints:
1 <= low.length, high.length <= 15lowandhighconsist of only digits.low <= highlowandhighdo not contain any leading zeros except for zero itself.
Approach overview
Problem Overview: Count how many numbers within a given range [low, high] are strobogrammatic. A strobogrammatic number looks the same when rotated 180 degrees (for example 69, 88, 101). The challenge is handling very large numbers represented as strings while efficiently generating only valid candidates.
Approach 1: Brute Force Enumeration (O(N * k), O(1) space)
Iterate through every number between low and high, convert each to a string, and check whether it remains the same after a strobogrammatic rotation. The check uses a mapping like {0↔0, 1↔1, 6↔9, 8↔8, 9↔6} while comparing characters from both ends. This method is straightforward but infeasible for large ranges because the number of candidates grows exponentially with digit length. Even moderate ranges quickly exceed practical limits.
Approach 2: Recursive Construction by Length (O(5^(n/2)) time, O(n) space)
Instead of checking every number, generate only valid strobogrammatic numbers using recursion. Build numbers from the center outward using valid digit pairs: (0,0), (1,1), (6,9), (8,8), (9,6). For odd lengths, allow middle digits 0, 1, and 8. Recursively construct all numbers for lengths between len(low) and len(high). Skip numbers with leading zero unless the length is one. Each generated string is then compared with the boundaries to ensure it falls inside the range. This drastically reduces the search space because every generated number is valid by construction.
Approach 3: Recursive Generation with Range Pruning (O(5^(n/2)) time, O(n) space)
An optimized variant integrates boundary checks during generation. While recursively filling positions from the outside inward, partial strings that already exceed the high prefix or fall below the low prefix can be discarded early. This pruning avoids building entire invalid numbers. The algorithm still relies on symmetric digit pairs and string comparisons, but it cuts unnecessary branches in the recursion tree. The technique combines array-style index manipulation with string boundary checks to keep the search efficient.
Recommended for interviews: Recursive construction is the expected solution. Brute force shows you understand the definition of strobogrammatic numbers, but it fails scalability constraints. Interviewers typically expect the recursive generation approach with valid digit pairs and length-based enumeration, optionally enhanced with boundary pruning for cleaner performance.
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.
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.
Let the lengths of low and high be a and b respectively.
Next, we traverse all lengths in the range [a,..b]. For each length n, we get all strobogrammatic numbers dfs(n), and then check whether they are in the range [low, high]. If they are, we increment the answer.
The time complexity is O(2^{n+2} times log n).
Similar problems:
class Solution:
def strobogrammaticInRange(self, low: str, high: str) -> int:
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
a, b = len(low), len(high)
low, high = int(low), int(high)
ans = 0
for n in range(a, b + 1):
for s in dfs(n):
if low <= int(s) <= high:
ans += 1
return ansclass Solution {
private static final int[][] PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
private int n;
public int strobogrammaticInRange(String low, String high) {
int a = low.length(), b = high.length();
long l = Long.parseLong(low), r = Long.parseLong(high);
int ans = 0;
for (n = a; n <= b; ++n) {
for (String s : dfs(n)) {
long v = Long.parseLong(s);
if (l <= v && v <= r) {
++ans;
}
}
}
return ans;
}
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;
}
}using ll = long long;
class Solution {
public:
const vector<pair<char, char>> pairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
int strobogrammaticInRange(string low, string high) {
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;
};
int a = low.size(), b = high.size();
int ans = 0;
ll l = stoll(low), r = stoll(high);
for (n = a; n <= b; ++n) {
for (auto& s : dfs(n)) {
ll v = stoll(s);
if (l <= v && v <= r) {
++ans;
}
}
}
return ans;
}
};func strobogrammaticInRange(low string, high string) int {
n := 0
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
}
a, b := len(low), len(high)
l, _ := strconv.Atoi(low)
r, _ := strconv.Atoi(high)
ans := 0
for n = a; n <= b; n++ {
for _, s := range dfs(n) {
v, _ := strconv.Atoi(s)
if l <= v && v <= r {
ans++
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Check | O(N * k) | O(1) | Small numeric ranges where generating every number is feasible |
| Recursive Generation by Length | O(5^(n/2)) | O(n) | General solution for large ranges represented as strings |
| Recursive Generation with Range Pruning | O(5^(n/2)) | O(n) | Best practical approach when boundaries are large and pruning reduces recursion |
Frequently asked questions
Is Strobogrammatic Number III easy or hard?
Strobogrammatic Number III is classified as Hard because it combines recursion, string-based numeric comparison, and combinatorial generation. Handling variable digit lengths and avoiding invalid leading zeros adds complexity. Efficient pruning and careful boundary checks are key to passing large test cases.
Strobogrammatic Number III Python/Java solution
Python and Java implementations typically use recursion to generate numbers from the center outward. The algorithm fills positions with valid strobogrammatic pairs, skips leading zeros, and checks whether the final string lies within the given bounds. The same logic easily translates to C++ and Go.
How to solve Strobogrammatic Number III in O(n)?
A true O(n) solution is not possible because you must enumerate possible strobogrammatic combinations. The closest optimal strategy is recursive generation, which builds only valid numbers and avoids scanning the entire numeric range. Its complexity is roughly O(5^(n/2)), far better than brute force enumeration.
What is the best approach for Strobogrammatic Number III?
Recursive generation of strobogrammatic numbers by length is the most effective approach. Instead of checking every value in the range, construct numbers using valid digit pairs such as (0,0), (1,1), (6,9), (8,8), and (9,6). Generate candidates for lengths between len(low) and len(high) and filter them against the range. This reduces the search space to O(5^(n/2)).
Is Strobogrammatic Number III asked at Google/Amazon/Meta?
Strobogrammatic problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test recursion, string manipulation, and combinatorial generation. Variants such as Strobogrammatic Number I, II, and III are common in interview prep platforms and coding rounds.
What data structure is used in Strobogrammatic Number III?
The solution primarily uses strings or character arrays to construct numbers symmetrically. A mapping of valid digit pairs like {0↔0, 1↔1, 6↔9, 8↔8, 9↔6} guides recursive placement. Recursion manages the generation process while comparing strings against the range boundaries.
What is the time complexity of Strobogrammatic Number III?
The optimal recursive approach runs in O(5^(n/2)) time, where n is the number of digits in the longest bound. Each recursive level adds symmetric digit pairs, producing at most five choices per outer position. Space complexity is O(n) due to recursion depth and temporary string construction.