Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Strobogrammatic Number III in Java: Count Numbers Between String Bounds

Count upside-down-symmetric numbers in an inclusive string range with paired-digit recursion, safe comparisons, commented Java and a dry run.

HardRecursion and backtrackingPattern: recursion, backtracking, two pointers

Problem statement

Given two strings low and high representing integers with low <= high, return the number of strobogrammatic numbers in the inclusive range [low, high].

A strobogrammatic number looks unchanged after a 180-degree rotation. Turning a number upside down both reverses its positions and rotates its digits. For example, 69 becomes 69, while 66 becomes 99 and is not valid.

This is the counting version of Strobogrammatic Number II. Number II returns every valid string of one length. Number III returns one count across a range, potentially spanning several lengths.

The supplied code assumes nonnegative decimal strings without leading zeros, except the single string "0". It also assumes the answer fits its int return type. These are important assumptions for the implementation, not invented numeric problem bounds. The public LeetCode problem is Premium; this article does not require an account to read the solution.

Constraints & requirements

CONTRACT
Assume low≤high, nonempty digit-only strings, no leading zeros except "0", and an answer that fits the supplied int return type. Numeric bounds were not publicly visible, so none are invented. LeetCode may require Premium.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    low="50"; high="100"
    Output
    3

    69, 88 and 96 are the three valid numbers. 11 is below low; all three-digit candidates exceed 100.

  2. Example 2 Case 2

    Input
    low="0"; high="0"
    Output
    1

    Single-digit 0 is valid and both endpoints are inclusive.

  3. Example 3 Case 3

    Input
    low="0"; high="1000"
    Output
    19

    There are 3 one-digit, 4 two-digit and 12 three-digit numbers. The smallest four-digit candidate, 1001, is too large.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

A left digit forces its rotated partner on the right; fill both ends together.

02Hint 2

Generate only lengths from low.length to high.length, handling an odd center separately.

03Hint 3

Return 1 or 0 at each completed candidate, compare lengths before text, and add every child count.

How to think before coding

Separate generation from the range filter. A call fills a compatible pair; an odd center is handled separately. A completed buffer contributes 1 only when low≤candidate≤high. Compare lengths BEFORE lexicographic digits, assuming canonical strings. Add every child and every permitted length. A local count avoids cross-call accumulation, while int count capacity remains a separate contract from string-bound safety.

Brute force and the improvement

Walk through every integer from low through high, rotate its digits, and count unchanged rotations. For R values and at most H digits per value, this needs O(R·H) time and O(H) working storage if string/big-number arithmetic is needed. Do not parse arbitrary-length bounds as int. The improved generator visits only strobogrammatic candidates of relevant lengths and checks inclusive bounds at completion. It avoids scanning the entire interval, but still enumerates candidates even when a narrow interval rejects most of them.

Intuition: build valid candidates, then check the range

Instead of checking every integer between low and high, build only numbers that can survive rotation.

Left digit Forced right digit Why it works
0 0 Zero rotates into itself
1 1 One rotates into itself
8 8 Eight rotates into itself
6 9 Rotation exchanges six and nine
9 6 Rotation exchanges nine and six

Choosing the left digit also chooses the right digit. For three positions, choosing the pair 6 ↔ 9 produces 6 _ 9. The center can be only 0, 1 or 8, giving 609, 619 and 689.

Two pointers, left and right, mark the next unfilled positions. Fill a compatible pair, then ask recursion to fill the smaller interior. When the pointers cross, the whole candidate is ready for a range check.

Why generate only certain lengths?

For canonical nonnegative numbers, more digits means a larger value. If low is "50" and high is "100", a one-digit number is too small and a four-digit number is too large. Only lengths two and three need to be generated.

That restriction does not mean every generated candidate is in range. 11 has an allowed length but is below 50. 101 also has an allowed length but is above 100. We still check both bounds at each completed candidate.

Why not convert the bounds to int?

The strings may represent values that do not fit in an int. Parsing them is unnecessary. Compare their lengths first, then compare their digits if the lengths are equal:

  • "99" has fewer digits than "100", so it is smaller.
  • "69" and "88" have equal lengths; their first differing digit decides their numeric order.
  • Comparing only text would incorrectly put "100" before "99".

This rule relies on the no-leading-zero assumption. "0009" is not numerically greater than "10", despite being longer. Normalize such inputs before using this algorithm if your own API accepts them.

Algorithm

  1. Try every length from low.length() through high.length(), inclusive.
  2. Allocate a reusable character buffer for that length.
  3. If left > right, compare the completed number with both bounds. Return 1 if it qualifies, otherwise 0.
  4. If left == right, try each self-rotating center: 0, 1 and 8. Add their counts and return.
  5. Otherwise, try every compatible pair. Skip an outer 00, which would create a leading zero.
  6. Fill both ends, recurse inward, and add the child’s count.

The center case runs before the pair loop. This allows the valid one-digit number 0 without allowing invalid multi-digit forms such as 00 or 0110.

Java solution

Generation and range comparison are separate helpers. The main(String[] args) invocation below runs all three visible examples without parsing either bound into a fixed-width integer.

Java
import java.util.*;

class Solution {
    private static final char[][] DATA = {
        {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
    }; // Left digit and the digit it becomes on the right after rotation.

    public static int strobogrammaticInRange(String low, String high) {
        int count = 0; // Local to this invocation; repeated calls do not share a count.
        for (int length = low.length(); length <= high.length(); length++) {
            char[] number = new char[length]; // Reuse this buffer within one length's search.
            count += generate(number, 0, length - 1, low, high); // Add ALL lengths, including endpoints.
        }
        return count; // Counts numbers, unlike Number II which returns a list of strings.
    }

    private static int generate(char[] number, int left, int right, String low, String high) {
        if (left > right) { // Every position has been assigned: this is one complete candidate.
            String candidate = new String(number); // Snapshot the filled buffer for comparison.
            return isInRange(candidate, low, high) ? 1 : 0; // Inclusive bounds; count once or reject.
        }
        if (left == right) { // Odd-length center must rotate into itself.
            int count = 0;
            for (char middle : new char[]{'0', '1', '8'}) { // 6 and 9 cannot be single centers.
                number[left] = middle; // Overwrite this call's own position for each sibling.
                count += generate(number, left + 1, right - 1, low, high);
            }
            return count; // Do NOT also run the pair loop on this same center position.
        }
        int count = 0;
        for (char[] pair : DATA) { // Every legal outer-pair branch contributes its own count.
            if (left == 0 && pair[0] == '0') continue; // Ban leading zero only for multi-digit numbers.
            number[left] = pair[0]; number[right] = pair[1]; // Choose both compatible ends together.
            count += generate(number, left + 1, right - 1, low, high); // Fill the smaller interior.
        }
        return count; // Returning inside the loop would lose all remaining pair branches.
    }

    private static boolean isInRange(String candidate, String low, String high) {
        return compareNumbers(candidate, low) >= 0 // Equality includes the lower endpoint.
                && compareNumbers(candidate, high) <= 0; // Equality includes the upper endpoint.
    }

    private static int compareNumbers(String first, String second) {
        // Contract: canonical nonnegative decimal strings; only "0" may start with zero.
        if (first.length() != second.length()) {
            return Integer.compare(first.length(), second.length()); // More digits means larger value.
        }
        return first.compareTo(second); // Equal-length digit strings have numeric lexicographic order.
    }

    public static void main(String[] args) {
        System.out.println(strobogrammaticInRange("50", "100")); // 3
        System.out.println(strobogrammaticInRange("0", "0")); // 1
        System.out.println(strobogrammaticInRange("0", "1000")); // 19
    }
}

The invocation prints 3, 1 and 19 on separate lines, matching the three examples above. Only a complete candidate becomes a String; we never store a list of all generated answers.

Recursion tree and dry run

Numbered illustrated dry run for Strobogrammatic Number III; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: low = "50", high = "100"

What to track: Track length, left/right, the char buffer and each frame’s local count. Bounds are tested only after every position is filled. This covers all 2-digit candidates and summarizes the longer length.

  1. Start the two-digit length

    Java operationcount += generate(number, 0, length - 1, low, high);
    Statelength = 2; wrapper count = 0; child left = 0, right = 1

    Only lengths from low.length() through high.length() can fall inside the range.

  2. Skip a leading zero, then fill 11

    Java operationif (left == 0 && pair[0] == '0') continue;
    State00 has no child; 11 creates a completed child with left = 1, right = 0

    The number buffer must represent a canonical multi-digit number, not "00".

  3. Reject a complete out-of-range candidate

    Java operationreturn isInRange(candidate, low, high) ? 1 : 0;
    Statecandidate = "11"; compareNumbers("11","50") < 0; return 0

    The waiting pair frame adds 0 and keeps trying; returning from that parent now would incorrectly lose later pairs.

  4. Add every successful sibling

    Java operationcount += generate(number, left + 1, right - 1, low, high);
    Statefill 88 → child returns 1; then 69 → 1; then 96 → 1; two-digit count = 3

    Each pair overwrites both buffer ends. Local count accumulates all three children instead of only the first success.

  5. Generate the three-digit length

    Java operationfor (char middle : new char[]{'0', '1', '8'})
    Stateouter pair 11 with centers 0,1,8 yields 101,111,181; each exceeds "100"

    The other outer pairs also exceed the high bound. All 12 valid three-digit candidates return 0; 6/9 are not legal single centers.

  6. Add length totals and return

    Java operationreturn count;
    Statewrapper count = 3 + 0 = 3

    Length-aware comparison avoids parsing large decimal strings or comparing unequal lengths lexicographically.

Final result: 3, for 88, 69 and 96; output is a count, not a generated list.

Here is the complete candidate grouping for low "50" and high "100". The code tries pairs in the order 00, 11, 88, 69, 96; the outer 00 branch is skipped.

Worked example · read from top to bottom
strobogrammaticInRange("50", "100")
├─ length 2: _ _
│  ├─ 00 → blocked before recursion: leading zero
│  ├─ 11 → below 50 → return 0
│  ├─ 88 → in range → return 1
│  ├─ 69 → in range → return 1
│  └─ 96 → in range → return 1
│  total for length 2 = 3
└─ length 3: _ _ _
   ├─ outer 00 → blocked
   ├─ 1 _ 1 → 101, 111, 181 → each returns 0
   ├─ 8 _ 8 → 808, 818, 888 → each returns 0
   ├─ 6 _ 9 → 609, 619, 689 → each returns 0
   └─ 9 _ 6 → 906, 916, 986 → each returns 0
   total for length 3 = 0
final count = 3 + 0 = 3

Each three-digit group actually has a center call with three leaf children. Every leaf is above 100, so none contributes to the answer. This is not a claim that range pruning stops those branches early: your implementation checks the range at the leaves.

Follow the accepted candidate 69

Moment Buffer / state What happens
Start this length _ _, left 0, right 1 Try a compatible outer pair
Choose 69 6 9 Fill both positions before calling the child
Child call left 1, right 0 Pointers crossed; make candidate "69"
Lower-bound check "69" versus "50" Same length; 69 is greater
Upper-bound check "69" versus "100" Fewer digits; 69 is smaller
Return Child returns 1 Parent adds 1 to its own local count
Next sibling Overwrite buffer with 9 6 Explore 96 without keeping the old 69

Why is there no explicit undo?

There is no growing shared list to remove from. Each sibling overwrites the positions that its call owns, and every deeper call fills its interior before reaching a leaf. Stale interior digits are never examined as a completed candidate before they have been overwritten.

The leaf’s new String(number) is an independent snapshot. Overwriting the buffer afterward cannot change that String. This differs from saving the mutable buffer itself.

Why add the returned counts?

The branches describe different numbers. If a child finds two qualifying numbers and another child finds three, the parent must return five. An immediate return generate(...) inside the pair loop would explore only its first allowed branch and miss the others.

For "0" through "0", the single center tries 0, 1 and 8. Their returned counts are 1, 0 and 0. Therefore the result is 1—not 0 and not 3.

Why it works

Validity: every filled pair agrees under rotation; an odd center rotates into itself. The leading-zero rule removes noncanonical multi-digit representations.

Completeness: every valid number in the range has a length between the two bound lengths. Its outer pair is one of the tried pairs; the same is true recursively for its interior. Its center, if any, is one of the three allowed digits. Its unique sequence of choices therefore reaches a leaf.

No duplicates: each distinct sequence of pair/center choices fills a different digit string. Different lengths cannot describe the same canonical integer because leading zeros are forbidden.

Correct counting: a leaf contributes exactly one if both inclusive comparisons pass, otherwise zero. Adding disjoint child counts and then length totals counts each qualifying number exactly once.

Complexity and alternative approaches

Let H be the number of digits in high. Let Pₗ be the number of canonical strobogrammatic candidates of length l:

  • For l=1, there are three: 0, 1 and 8.
  • For even l=2k, there are 4 × 5^(k−1): four nonzero outer pairs, then five choices for every inner pair.
  • For odd l=2k+1 with l≥3, multiply that count by three for the center.

The method visits candidates for every generated length, even when most fail the range check. Creating each leaf String costs O(l), so time is O(Σ l·Pₗ) over lengths from low to high. A convenient upper bound is O(H·5^floor(H/2)). A narrow numerical range does not automatically make this version fast.

Auxiliary space is O(H) for the buffer, recursive frames and current candidate String. Different lengths are processed sequentially. The result is one integer, not an output-sized list. Recursion is not constant-space merely because the method returns a count.

Other approaches have different tradeoffs:

  • Check every integer: simple for tiny ranges, but needs roughly range-width × digit-length work and safe large-number arithmetic.
  • Generate with Number II, then filter: reuses an existing generator, but unnecessarily stores every candidate when only a count is needed.
  • Bound-aware combinatorial counting: count free interiors without constructing every leaf, then handle boundary choices carefully. It is more scalable but requires reasoning about the forced mirrored suffix, not just a naive prefix comparison.

String comparison protects the bounds from parsing overflow; it does not protect the count from int overflow. For a wider application contract, choose a suitable long/BigInteger count or checked additions, and reconsider exponential generation. No unrestricted huge-input performance guarantee is made for this teaching implementation.

Common mistakes

  • Using ordinary string comparison before checking digit lengths.
  • Rejecting every zero and losing the valid number 0 or inner zeros in 101.
  • Allowing 6 or 9 at an odd center.
  • Letting the pair loop also run after handling the center.
  • Returning from the first pair instead of accumulating all child counts.
  • Using strict inequalities and excluding a valid endpoint such as [69,69].
  • Confusing a palindrome with a strobogrammatic number: 69 passes, while 66 fails.
  • Assuming a small answer means only a small number of candidates were generated.

Useful revision checks: [69,69] → 1, [100,100] → 0, [101,101] → 1, and [0,10] → 3.

Practice next

Next lessonStrobogrammatic Number II

Back to Recursion and backtracking →