Watch 10 video solutions for Strobogrammatic Number III, a hard level problem involving Array, String, Recursion. This walkthrough by Greg Hogg has 109,937 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 15low and high consist of only digits.low <= highlow and high do not contain any leading zeros except for zero itself.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.
| 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 |