LeetCode 248 - Strobogrammatic Number III

The problem asks us to count how many numbers within the inclusive range [low, high] are strobogrammatic. A strobogrammatic number is a number that appears unchanged when rotated 180 degrees.

leetcodehardarraystringrecursion

LeetCode Problem 248

Difficulty: 🔴 Hard
Topics: Array, String, Recursion

Solution

Problem Understanding

The problem asks us to count how many numbers within the inclusive range [low, high] are strobogrammatic.

A strobogrammatic number is a number that appears unchanged when rotated 180 degrees. Only certain digits remain valid after rotation:

Original Rotated
0 0
1 1
6 9
8 8
9 6

For example, "69" becomes "96" after rotation, but since the entire number flips positionally, the rotated result still visually represents the same number. Therefore "69" is strobogrammatic.

The input consists of two strings, low and high, rather than integers. This is important because the numbers may contain up to 15 digits, and the problem wants us to work carefully with leading zeros and lexicographical comparisons. The goal is to count every valid strobogrammatic number whose numeric value lies between low and high, inclusive.

The constraints are small enough that generating all valid strobogrammatic numbers of lengths between len(low) and len(high) is feasible. However, brute forcing every integer in the range is completely impractical because the range could span numbers as large as 10^15.

Several edge cases are important:

  • The number "0" is valid and must be counted correctly.
  • Numbers cannot contain leading zeros unless the number itself is exactly "0".
  • The range boundaries may themselves be strobogrammatic.
  • Single digit numbers only allow 0, 1, and 8.
  • Odd length numbers must have a valid center digit, which can only be 0, 1, or 8.

Understanding these constraints is the key to building an efficient recursive generation solution.

Approaches

Brute Force Approach

A straightforward approach would be to iterate through every number from low to high, convert each number into a string, rotate it digit by digit, and check whether the rotated result equals the original number.

To validate a number, we could use a mapping:

0 -> 0
1 -> 1
6 -> 9
8 -> 8
9 -> 6

For each digit, we would build the rotated string in reverse order and compare it to the original string.

This approach is correct because it explicitly checks every number in the range. However, it is far too slow. The range can be enormous, potentially close to 10^15, which makes iterating through every integer impossible within time limits.

Optimal Approach

The key observation is that strobogrammatic numbers have a very strict structure. Instead of checking every number, we can directly generate only valid strobogrammatic numbers.

We construct numbers recursively from the inside outward using valid digit pairs:

Left Right
0 0
1 1
6 9
8 8
9 6

For example, if we already know "11" is valid, we can create larger valid numbers such as:

  • "0110"
  • "1111"
  • "6119"
  • "8118"
  • "9116"

We recursively generate all strobogrammatic numbers of lengths between len(low) and len(high), then filter out:

  • Numbers with leading zeros
  • Numbers outside the target range

This dramatically reduces the search space because we only generate valid candidates.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × D) O(D) Checks every number in the range
Optimal O(5^(n/2)) O(n) Generates only valid strobogrammatic numbers

Here, N is the numeric size of the range and D is the number of digits. In the optimal approach, n is the maximum digit length.

Algorithm Walkthrough

  1. Define all valid strobogrammatic digit pairs.

We store the five valid rotation pairs:

(0,0), (1,1), (6,9), (8,8), (9,6)

These pairs are the only digits that remain valid after 180 degree rotation. 2. Build a recursive helper function.

The helper generates all strobogrammatic strings of a given length.

The recursion works from the inside outward. If we know all valid strings of length n - 2, we can surround them with valid digit pairs to build strings of length n. 3. Handle the base cases.

There are two important base cases:

  • Length 0 returns [""]
  • Length 1 returns ["0", "1", "8"]

Single digit numbers can only use digits that rotate to themselves. 4. Recursively construct larger numbers.

For each smaller valid string, prepend and append each valid pair.

Example:

inner = "1"

-> "101"
-> "111"
-> "619"
-> "818"
-> "916"
  1. Avoid leading zeros.

We must reject numbers like "0110" because leading zeros are not allowed.

However, "0" itself is valid.

We enforce this by disallowing the pair (0,0) at the outermost level unless the entire number length is 1. 6. Generate numbers for all relevant lengths.

We generate strobogrammatic numbers for every length from:

len(low) to len(high)
  1. Filter numbers by range.

After generating a candidate:

  • If its length equals len(low), ensure it is at least low
  • If its length equals len(high), ensure it is at most high
  1. Count valid numbers.

Every remaining candidate contributes to the final answer.

Why it works

The recursive construction guarantees correctness because every generated number is formed exclusively from valid rotational digit pairs. Since each recursive step preserves the strobogrammatic property, every produced number is valid. Conversely, every valid strobogrammatic number can be decomposed into smaller valid inner substrings surrounded by one of the allowed pairs, which means the recursion generates all possible valid numbers exactly once.

Python Solution

class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        pairs = [
            ('0', '0'),
            ('1', '1'),
            ('6', '9'),
            ('8', '8'),
            ('9', '6')
        ]

        def build(length: int, total_length: int) -> list[str]:
            if length == 0:
                return [""]

            if length == 1:
                return ["0", "1", "8"]

            result = []

            for middle in build(length - 2, total_length):
                for left, right in pairs:
                    if length == total_length and left == '0':
                        continue

                    result.append(left + middle + right)

            return result

        count = 0

        for length in range(len(low), len(high) + 1):
            candidates = build(length, length)

            for num in candidates:
                if length == len(low) and num < low:
                    continue

                if length == len(high) and num > high:
                    continue

                count += 1

        return count

The implementation begins by defining the valid rotational digit pairs. These are the only pairs allowed when constructing strobogrammatic numbers.

The recursive build() function generates all valid strobogrammatic strings of a specific length. The parameter total_length is necessary because we must detect the outermost recursive layer in order to prevent leading zeros.

The base case for length 0 returns an empty string. This acts as the foundation for constructing even length numbers. The base case for length 1 returns "0", "1", and "8" because these are the only valid middle digits for odd length numbers.

The recursive step generates smaller valid strings and surrounds them with valid digit pairs. When constructing the outermost layer, the pair ('0', '0') is skipped to avoid invalid leading zeros.

After generating all candidates of a particular length, the algorithm compares each candidate against the boundaries low and high. Since all strings being compared have equal length, lexicographical comparison works correctly.

Finally, the algorithm returns the total count.

Go Solution

func strobogrammaticInRange(low string, high string) int {
	pairs := [][2]byte{
		{'0', '0'},
		{'1', '1'},
		{'6', '9'},
		{'8', '8'},
		{'9', '6'},
	}

	var build func(int, int) []string

	build = func(length int, totalLength int) []string {
		if length == 0 {
			return []string{""}
		}

		if length == 1 {
			return []string{"0", "1", "8"}
		}

		var result []string

		middles := build(length-2, totalLength)

		for _, middle := range middles {
			for _, pair := range pairs {
				left := pair[0]
				right := pair[1]

				if length == totalLength && left == '0' {
					continue
				}

				result = append(result,
					string(left)+middle+string(right))
			}
		}

		return result
	}

	count := 0

	for length := len(low); length <= len(high); length++ {
		candidates := build(length, length)

		for _, num := range candidates {
			if length == len(low) && num < low {
				continue
			}

			if length == len(high) && num > high {
				continue
			}

			count++
		}
	}

	return count
}

The Go implementation follows the same recursive structure as the Python version. One notable difference is that Go does not have tuple literals, so the digit pairs are stored as arrays of two bytes.

String concatenation requires converting bytes into strings explicitly using string(left) and string(right).

Go slices are used dynamically for storing generated candidates. Since the maximum length is only 15, recursion depth remains small and safe.

Worked Examples

Example 1

Input:
low = "50"
high = "100"

We generate all strobogrammatic numbers of lengths 2 and 3.

Length 2 Generation

Inner Pair Result
"" 1,1 11
"" 6,9 69
"" 8,8 88
"" 9,6 96

00 is skipped because leading zeros are not allowed.

Now compare against range:

Number In Range?
11 No
69 Yes
88 Yes
96 Yes

Current count = 3

Length 3 Generation

Generated candidates include:

101
111
181
609
619
689
808
818
888
906
916
986

All exceed "100".

Final answer:

3

Example 2

Input:
low = "0"
high = "0"

Length 1 Generation

Candidate Valid?
0 Yes
1 No
8 No

Final count:

1

Complexity Analysis

Measure Complexity Explanation
Time O(5^(n/2)) Generates all valid strobogrammatic numbers
Space O(n) Recursive call stack depth

The recursion builds numbers two digits at a time. Each recursive layer has at most five branching choices, so the number of generated candidates grows approximately as 5^(n/2).

This is dramatically smaller than iterating through every integer up to 10^15.

The recursion depth is proportional to the digit length n, which is at most 15.

Test Cases

sol = Solution()

assert sol.strobogrammaticInRange("50", "100") == 3
# Standard multi-number range

assert sol.strobogrammaticInRange("0", "0") == 1
# Single valid number

assert sol.strobogrammaticInRange("1", "1") == 1
# Single digit strobogrammatic

assert sol.strobogrammaticInRange("2", "2") == 0
# Single digit non-strobogrammatic

assert sol.strobogrammaticInRange("0", "1") == 2
# Includes both 0 and 1

assert sol.strobogrammaticInRange("0", "10") == 3
# Valid numbers are 0, 1, 8

assert sol.strobogrammaticInRange("10", "69") == 2
# Valid numbers are 11 and 69

assert sol.strobogrammaticInRange("100", "1000") == 12
# Multiple three-digit numbers

assert sol.strobogrammaticInRange("888", "888") == 1
# Exact boundary match

assert sol.strobogrammaticInRange("999", "10000") > 0
# Crosses digit lengths

assert sol.strobogrammaticInRange("6", "9") == 1
# Only 8 is valid in this range

assert sol.strobogrammaticInRange("11", "11") == 1
# Exact two-digit valid number

assert sol.strobogrammaticInRange("68", "96") == 3
# Includes 69, 88, 96
Test Why
"50" to "100" Standard example
"0" to "0" Smallest valid input
"1" to "1" Single digit valid
"2" to "2" Single digit invalid
"0" to "1" Multiple single-digit results
"0" to "10" Boundary transition
"10" to "69" Includes multiple valid two-digit numbers
"100" to "1000" Three-digit recursion coverage
"888" to "888" Exact boundary equality
"999" to "10000" Cross-length range
"6" to "9" Invalid boundary digits
"11" to "11" Exact valid pair
"68" to "96" Mixed range filtering

Edge Cases

One important edge case is the handling of leading zeros. During recursive construction, pairs like ('0', '0') naturally generate strings such as "0110". These are not valid numeric representations according to the problem statement. A naive implementation might accidentally count them. The solution avoids this by explicitly rejecting outermost constructions that begin with '0', while still allowing the single digit "0" itself.

Another critical edge case involves odd length numbers. In odd length strobogrammatic numbers, the center digit must remain unchanged after rotation. Only 0, 1, and 8 satisfy this property. Digits like 6 and 9 cannot appear in the center because they rotate into each other. The recursive base case for length 1 correctly restricts the middle choices.

A third subtle edge case is lexicographical comparison between strings. Comparing numeric strings lexicographically only works when the strings have the same length. The implementation carefully performs boundary checks only when candidate lengths match the lengths of low or high. This guarantees correct numeric ordering without integer conversion.

A final edge case occurs when the range spans multiple digit lengths, such as "99" to "1001". A naive implementation might miss numbers of intermediate lengths or mishandle comparisons across different digit counts. The solution explicitly generates candidates for every length between len(low) and len(high), ensuring complete coverage of the range.