Skip to main content
Talentd

Strobogrammatic Number III - Solution & Explanation

HardPremiumFree on FleetCodeArrayStringRecursion9 min read
Practice this problem

Problem Statement

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 <= 15
  • low and high consist of only digits.
  • low <= high
  • low and high do 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:

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range CheckO(N * k)O(1)Small numeric ranges where generating every number is feasible
Recursive Generation by LengthO(5^(n/2))O(n)General solution for large ranges represented as strings
Recursive Generation with Range PruningO(5^(n/2))O(n)Best practical approach when boundaries are large and pruning reduces recursion

Video Solution

LeetCode 248. Strobogrammatic Number III • Happy Coding • 1,868 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Strobogrammatic Number III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Strobogrammatic Number

Next

Strobogrammatic Number II