LeetCode 2801 - Count Stepping Numbers in Range

The problem asks us to count how many integers in the inclusive range [low, high] are stepping numbers. A stepping number is defined as a number where every pair of adjacent digits differs by exactly 1.

leetcodehardstringdynamic-programming

LeetCode Problem 2801

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many integers in the inclusive range [low, high] are stepping numbers.

A stepping number is defined as a number where every pair of adjacent digits differs by exactly 1. For example:

  • 123454321 is a stepping number because every adjacent pair differs by 1
  • 10 is a stepping number because |1 - 0| = 1
  • 98 is a stepping number because |9 - 8| = 1
  • 11 is not a stepping number because |1 - 1| = 0
  • 135 is not a stepping number because |1 - 3| = 2

The input numbers are given as strings instead of integers because they can be extremely large, up to 10^100. That means normal integer iteration is impossible. We cannot simply loop from low to high and test each number individually.

The task is to return the number of valid stepping numbers within the range, modulo 10^9 + 7.

The constraints immediately suggest that brute force enumeration is infeasible:

  • high can contain up to 100 digits
  • The numeric range may therefore be astronomically large
  • We need a digit-based dynamic programming solution instead of explicit enumeration

A few important observations and edge cases stand out immediately:

  • Numbers cannot contain leading zeros
  • Single-digit numbers are always stepping numbers because there are no adjacent digits to violate the rule
  • The range boundaries themselves may or may not be stepping numbers
  • We must correctly handle ranges spanning different digit lengths
  • Very large inputs require string-based digit processing rather than numeric arithmetic

The core challenge is counting valid numbers efficiently without generating every integer in the range.

Approaches

Brute Force Approach

The most direct approach would be:

  1. Convert low and high into integers
  2. Iterate through every number in the range
  3. Check whether each number is a stepping number
  4. Count the valid ones

To verify whether a number is stepping:

  • Convert it into digits
  • Compare every adjacent pair
  • Ensure every absolute difference equals 1

This approach is correct because it explicitly validates every number in the range. However, it is completely impractical for the given constraints.

If high contains up to 100 digits, the range size could be close to 10^100, which is computationally impossible to iterate through.

Optimal Approach, Digit DP

The key insight is that we do not need to enumerate every number individually.

Instead, we can build valid numbers digit by digit while enforcing the stepping constraint during construction.

This naturally leads to Digit Dynamic Programming, often called Digit DP.

The idea is:

  • Count how many stepping numbers are less than or equal to a given bound
  • Then compute:

$$\text{count}(high) - \text{count}(low - 1)$$

To count valid numbers up to a limit:

  • Process the number from left to right

  • At each digit position:

  • Decide which digit to place

  • Respect the upper bound constraint

  • Respect the stepping-number adjacency rule

  • Use memoization to avoid recomputing identical states

The DP state needs to track:

  • Current digit index
  • Previous digit chosen
  • Whether we are still limited by the upper bound
  • Whether we have started building a non-leading-zero number

Because the number length is at most 100, the total number of DP states is very small.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((high - low) × D) O(D) Explicitly checks every number
Optimal O(D × 10 × 2 × 2 × 11) O(D × 10 × 2 × 2) Uses Digit DP with memoization

Here, D is the number of digits, at most 100.

Algorithm Walkthrough

Step 1: Create a helper function count(limit)

We first define a function that counts how many stepping numbers are less than or equal to a given string limit.

This transforms the original range problem into:

$$\text{answer} = \text{count}(high) - \text{count}(low - 1)$$

Step 2: Use digit DP

We process the digits from left to right.

At each position, we decide which digit to place.

The recursive DP state contains:

  1. index
  • Current digit position
  1. prev_digit
  • Previously chosen digit
  • Needed to verify the stepping condition
  1. tight
  • Whether the current prefix exactly matches the limit
  • If true, the next digit cannot exceed the corresponding digit in the limit
  1. started
  • Whether we have placed a non-leading-zero digit yet
  • Needed because leading zeros should not participate in the stepping constraint

Step 3: Handle leading zeros carefully

Before the number starts:

  • We may continue placing zeros
  • These zeros are treated as "empty positions"
  • They do not trigger the stepping condition

Once the first non-zero digit is placed:

  • Every subsequent digit must differ from the previous digit by exactly 1

Step 4: Enforce the stepping constraint

If the number has already started:

  • The next digit is valid only if:

$$|digit - prev_digit| = 1$$

This guarantees the final number is a stepping number.

Step 5: Memoize DP states

Many recursive states repeat.

For example:

  • Same position
  • Same previous digit
  • Same tight state
  • Same started state

will always produce the same result.

Memoization reduces exponential recursion into a small polynomial number of states.

Step 6: Compute low - 1

To count numbers inside [low, high], we compute:

$$\text{count}(high) - \text{count}(low - 1)$$

Since inputs are strings, we implement manual string subtraction.

Step 7: Return modulo 10^9 + 7

All intermediate results are computed modulo:

$$10^9 + 7$$

to avoid overflow and satisfy the problem requirement.

Why it works

The DP explores every valid number digit by digit while pruning invalid choices immediately.

The tight flag guarantees we never exceed the bound. The started flag correctly handles leading zeros. The adjacency check guarantees every constructed number satisfies the stepping property.

Because every valid number corresponds to exactly one DP path, and every DP path constructs exactly one valid number, the algorithm counts all valid stepping numbers exactly once.

Python Solution

from functools import lru_cache

MOD = 10**9 + 7

class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:

        def subtract_one(num: str) -> str:
            if num == "0":
                return "0"

            digits = list(num)
            i = len(digits) - 1

            while i >= 0:
                if digits[i] != '0':
                    digits[i] = str(int(digits[i]) - 1)
                    break
                digits[i] = '9'
                i -= 1

            result = ''.join(digits).lstrip('0')
            return result if result else "0"

        def count_up_to(limit: str) -> int:
            digits = list(map(int, limit))
            n = len(digits)

            @lru_cache(None)
            def dp(index: int, prev_digit: int, tight: bool, started: bool) -> int:
                if index == n:
                    return 1 if started else 0

                upper = digits[index] if tight else 9
                total = 0

                for digit in range(upper + 1):
                    next_tight = tight and (digit == upper)

                    if not started:
                        if digit == 0:
                            total += dp(
                                index + 1,
                                -1,
                                next_tight,
                                False
                            )
                        else:
                            total += dp(
                                index + 1,
                                digit,
                                next_tight,
                                True
                            )
                    else:
                        if abs(digit - prev_digit) == 1:
                            total += dp(
                                index + 1,
                                digit,
                                next_tight,
                                True
                            )

                return total % MOD

            return dp(0, -1, True, False)

        low_minus_one = subtract_one(low)

        result = (
            count_up_to(high)
            - count_up_to(low_minus_one)
        ) % MOD

        return result

The implementation begins with the subtract_one helper, which decrements a numeric string without converting it into a large integer. This is necessary because the input length can reach 100 digits.

The main logic resides inside count_up_to. This function counts all stepping numbers less than or equal to a given limit.

The recursive DP function processes the number one digit at a time.

The index parameter tracks the current position. The prev_digit parameter stores the previously chosen digit so we can verify the stepping constraint. The tight flag ensures we never exceed the upper bound. The started flag distinguishes between leading zeros and actual digits.

If we have not started building the number yet, we may either:

  • Continue skipping digits with leading zeros
  • Start the number with a non-zero digit

Once the number has started, every next digit must differ from the previous digit by exactly 1.

Memoization via lru_cache prevents recomputation of repeated states.

Finally, we compute:

count(high) - count(low - 1)

which gives the number of stepping numbers inside the inclusive range.

Go Solution

package main

const MOD int = 1000000007

func countSteppingNumbers(low string, high string) int {

	subtractOne := func(num string) string {
		if num == "0" {
			return "0"
		}

		digits := []byte(num)
		i := len(digits) - 1

		for i >= 0 {
			if digits[i] != '0' {
				digits[i]--
				break
			}
			digits[i] = '9'
			i--
		}

		start := 0
		for start < len(digits) && digits[start] == '0' {
			start++
		}

		if start == len(digits) {
			return "0"
		}

		return string(digits[start:])
	}

	var countUpTo func(string) int

	countUpTo = func(limit string) int {
		digits := []byte(limit)
		n := len(digits)

		type State struct {
			index     int
			prevDigit int
			tight     int
			started   int
		}

		memo := map[State]int{}

		var dp func(int, int, int, int) int

		dp = func(index int, prevDigit int, tight int, started int) int {

			if index == n {
				if started == 1 {
					return 1
				}
				return 0
			}

			state := State{
				index,
				prevDigit,
				tight,
				started,
			}

			if tight == 0 {
				if val, exists := memo[state]; exists {
					return val
				}
			}

			upper := 9
			if tight == 1 {
				upper = int(digits[index] - '0')
			}

			total := 0

			for digit := 0; digit <= upper; digit++ {

				nextTight := 0
				if tight == 1 && digit == upper {
					nextTight = 1
				}

				if started == 0 {

					if digit == 0 {
						total += dp(
							index+1,
							-1,
							nextTight,
							0,
						)
					} else {
						total += dp(
							index+1,
							digit,
							nextTight,
							1,
						)
					}

				} else {

					if abs(digit-prevDigit) == 1 {
						total += dp(
							index+1,
							digit,
							nextTight,
							1,
						)
					}
				}

				total %= MOD
			}

			if tight == 0 {
				memo[state] = total
			}

			return total
		}

		return dp(0, -1, 1, 0)
	}

	lowMinusOne := subtractOne(low)

	result := (countUpTo(high) - countUpTo(lowMinusOne)) % MOD

	if result < 0 {
		result += MOD
	}

	return result
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version but uses explicit memoization with a map because Go does not provide built-in memoization decorators like lru_cache.

The DP state is represented with a struct so it can be used as a map key efficiently.

Go also requires careful handling of negative modulo results. After subtraction, we add MOD if the result becomes negative.

String manipulation uses byte slices for efficiency.

Worked Examples

Example 1

Input:

low = "1"
high = "11"

We compute:

count(11) - count(0)

Counting stepping numbers up to 11

Number Stepping? Reason
1 Yes Single digit
2 Yes Single digit
3 Yes Single digit
4 Yes Single digit
5 Yes Single digit
6 Yes Single digit
7 Yes Single digit
8 Yes Single digit
9 Yes Single digit
10 Yes |1 - 0| = 1
11 No |1 - 1| = 0

Total:

10

DP Trace

At index 0:

Chosen Digit Started Valid
0 No Continue
1 Yes Allowed

From prefix 1:

Next Digit Difference Valid
0 1 Yes
1 0 No

Valid constructed numbers:

1
10

Combined with all single-digit numbers, total becomes 10.

Example 2

Input:

low = "90"
high = "101"

We compute:

count(101) - count(89)

Stepping numbers inside range

Number Valid? Reason
98 Yes |9 - 8| = 1
101 Yes |1 - 0| = 1 and |0 - 1| = 1

Answer:

2

DP Construction for 101

Starting with digit 1:

Current Prefix Next Allowed Digits
1 0, 2
10 1
101 Complete valid number

The DP successfully builds 101.

Complexity Analysis

Measure Complexity Explanation
Time O(D × 10 × 11 × 2 × 2) Each DP state tries at most 10 digits
Space O(D × 11 × 2 × 2) Memoization table size

Here, D is the number of digits in the bound, at most 100.

The number of DP states is very small because:

  • index ranges over at most 100
  • prev_digit has only 11 possibilities including -1
  • tight has 2 states
  • started has 2 states

Each state explores at most 10 digit choices.

This makes the solution extremely efficient even for 100 digit inputs.

Test Cases

sol = Solution()

assert sol.countSteppingNumbers("1", "11") == 10  # example 1
assert sol.countSteppingNumbers("90", "101") == 2  # example 2

assert sol.countSteppingNumbers("1", "1") == 1  # single digit
assert sol.countSteppingNumbers("2", "2") == 1  # another single digit
assert sol.countSteppingNumbers("10", "10") == 1  # valid two-digit stepping
assert sol.countSteppingNumbers("11", "11") == 0  # invalid two-digit number

assert sol.countSteppingNumbers("98", "98") == 1  # valid descending step
assert sol.countSteppingNumbers("99", "99") == 0  # equal adjacent digits

assert sol.countSteppingNumbers("100", "100") == 0  # 1->0 valid, 0->0 invalid
assert sol.countSteppingNumbers("101", "101") == 1  # valid three-digit stepping

assert sol.countSteppingNumbers("0", "0") == 0  # no positive stepping number
assert sol.countSteppingNumbers("1", "9") == 9  # all single digits valid

assert sol.countSteppingNumbers("10", "15") == 2  # only 10 and 12
assert sol.countSteppingNumbers("20", "25") == 2  # 21 and 23

assert sol.countSteppingNumbers("1000", "1100") > 0  # larger range
assert sol.countSteppingNumbers("1", "100000") > 0  # stress test

Test Summary

Test Why
"1", "11" Verifies sample case
"90", "101" Verifies multi-digit transitions
"1", "1" Smallest positive range
"11", "11" Invalid repeated digits
"98", "98" Descending stepping number
"100", "100" Fails because of repeated zero
"101", "101" Valid alternating pattern
"1", "9" All single digits valid
"10", "15" Mixed valid and invalid numbers
"1000", "1100" Larger digit lengths
"1", "100000" Stress test for DP

Edge Cases

One important edge case is single-digit numbers. Every single-digit number is automatically a stepping number because there are no adjacent digits to compare. A buggy implementation might incorrectly reject them by assuming at least one adjacency check is required. The DP handles this naturally because once a non-zero digit is placed and the recursion ends, the number is counted as valid.

Another important edge case involves leading zeros. During digit construction, the DP may temporarily place zeros before the number officially starts. These zeros must not participate in the stepping constraint. For example, while constructing 101, the internal representation may pass through prefixes like 001. The started flag ensures leading zeros are ignored until the first non-zero digit appears.

A third tricky edge case occurs when computing low - 1. Since inputs are strings and may contain many digits, normal integer subtraction is impossible. Cases like "1000" require borrow propagation to produce "999". The helper function performs manual subtraction digit by digit and removes leading zeros correctly.

Another subtle edge case is repeated zeros inside the number. For example, 100 is not a stepping number because:

|1 - 0| = 1
|0 - 0| = 0

The adjacency check inside the DP guarantees these invalid sequences are rejected immediately.

Finally, extremely large bounds such as 10^100 would overflow normal numeric types in most languages. Because the solution processes numbers as strings and works digit by digit, it handles arbitrarily large inputs safely and efficiently.