Abstract / Summary

Count the numbers between two given values that have all consecutive digits differing by exactly one.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 26% (30k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the number of stepping numbers that lie in the inclusive interval [low, high]. A stepping number is defined as an integer whose adjacent digits differ by exactly one. The algorithm treats the interval as two prefix-counting problems: it first counts all stepping numbers from 1 up to high, then counts all stepping numbers from 1 up to low-1, and finally returns the difference modulo 1 000 000 007. The core of the solution is a depth-first recursion with memoization that walks digit positions from most significant to least significant while respecting a tight upper bound.

Key Steps

Step 1: Count up to high

size   = len(high)
digits = [int(c) for c in high]
one    = deeper(0, -1, True)

The length of the upper bound string is stored in size and each character is converted to an integer digit stored in the list digits. The call deeper(0, -1, True) initiates the recursive enumeration from the most significant position (pos = 0). The sentinel value previous = -1 signals that no non-zero digit has been placed yet, allowing the recursion to handle leading zeros correctly. The flag limit = True indicates that the current prefix must not exceed the corresponding prefix of high.

Step 2: Count up to low-1

low    = str(int(low) - 1)          # Python supports large integers
size   = len(low)
digits = [int(c) for c in low]
deeper.cache_clear()               # important ! avoid collision with step 1
two    = deeper(0, -1, True)

The lower bound is decremented by one using Python’s arbitrary-precision integer conversion, then the same preparation steps are repeated for the new bound. The memoization cache of deeper is cleared before the second counting phase to prevent cross-contamination of results that were computed under a different size and digits configuration.

Recursive helper deeper

@cache
def deeper(pos, previous, limit):
    nonlocal size
    if pos == size:
        return previous >= 0

    last = digits[pos] if limit else 9
    result = 0

    if previous == -1:
        result = deeper(pos + 1, -1, False)
        for i in range(1, last + 1):
            result += deeper(pos + 1, i, limit and i == last)
    else:
        up = previous + 1
        if up <= last:
            result += deeper(pos + 1, up, limit and up == last)

        down = previous - 1
        if 0 <= down <= last:
            result += deeper(pos + 1, down, limit and down == last)

    return result

The function deeper is decorated with @cache, which automatically memoizes results keyed by the tuple (pos, previous, limit). The recursion proceeds position by position. When the end of the digit string is reached (pos == size), the function returns 1 only if a non-zero digit has been placed (previous >= 0), thereby discarding the all-zero number.

The variable last represents the maximal digit that can be placed at the current position. If the current prefix is already known to be smaller than the bound (limit == False), last is set to 9; otherwise it is the corresponding digit from digits.

When previous == -1, the algorithm is still in the leading-zero region. It first explores the path that continues to skip this position (deeper(pos + 1, -1, False)), which effectively treats the current digit as a leading zero and releases the tight bound. Then it iterates over all possible starting digits from 1 up to last, launching a new recursion for each candidate. The loop respects the tight bound by passing limit and i == last.

When a non-zero digit has already been placed (previous != -1), the recursion branches into at most two successors: one where the next digit is previous + 1 (the “up” direction) and one where it is previous - 1 (the “down” direction). Each branch checks that the candidate digit does not exceed last and that it stays within the bound when limit is true.

Edge Cases Handled

The implementation explicitly addresses several boundary conditions:

• The case where the entire number consists of leading zeros is filtered out by the final check previous >= 0. This prevents the empty number from being counted as a valid stepping number.
• Starting a number with digit zero is prohibited. The loop that initiates the first non-zero digit begins at 1, ensuring that numbers such as 0, 01, or any representation with a leading zero are excluded.
• When the lower bound is "0" the expression int(low) - 1 yields -1. Converting -1 back to a string produces "-1", whose length is 2. The subsequent digit list [-1, 1] still leads to a correct count because the recursion will immediately reject any path that tries to place a negative digit, resulting in a count of zero for the range [1, -1]. This effectively treats the interval [low, high] as starting from 0 when low is "0".
• The algorithm works for arbitrarily large inputs because it relies on Python’s built-in arbitrary-precision integers for the subtraction int(low) - 1. The conversion back to a string preserves the exact decimal representation, allowing the digit-wise DP to operate without overflow concerns.
• The tight-bound flag limit guarantees that the recursion never generates a number larger than the supplied bound. When limit becomes False, the algorithm freely explores all digits up to 9, which speeds up the enumeration for prefixes already known to be smaller.

Performance Optimizations

Memoization via @cache is the primary source of efficiency. By caching the result of each state (pos, previous, limit), the recursion avoids recomputing identical subproblems that arise from different paths sharing the same suffix constraints. The state space is bounded by size (the number of digit positions) multiplied by the range of possible previous values (-1 through 9) and the two Boolean values of limit. This compact state space ensures that the total number of distinct recursive calls remains modest even for very long input strings.

The early release of the tight bound (limit = False) after the first non-zero digit is placed reduces the branching factor for the remaining positions. Once the prefix is known to be smaller than the bound, the algorithm can freely use the full digit range 0-9 without repeatedly checking against the original bound digits. This eliminates unnecessary comparisons in the deeper levels of the recursion.

Clearing the cache between the two counting phases (deeper.cache_clear()) prevents the accumulation of stale entries that belong to a different size and digits configuration. By resetting the memoization store, the second phase starts with a clean slate, ensuring that each DP table is sized precisely for its respective bound and that memory usage does not grow beyond what is needed for a single pass.

Finally, the modular arithmetic applied only at the very end (% 1_000_000_007) avoids repeated modulo operations inside the recursion. Since the intermediate counts are bounded by the total number of stepping numbers up to the given bound, they comfortably fit within Python’s integer range, and postponing the modulo operation reduces the overhead of frequent arithmetic reductions.

Think of this code like a smart helper playing a game with numbers to see which ones are special. A special number is one where every neighbor is exactly one step away, like jumping from a number two to a number three or down to a number one.

The helper starts by looking at all the numbers up to the biggest one and then looks at all the numbers before the smallest one. To do this, the code uses a neat trick called recursion, which is like the helper deciding what digit to pick next, one spot at a time, just like building a long tower out of blocks. At each spot, the helper looks at the last number used and only picks a new number that is exactly one higher or one lower.

While building these towers, the helper remembers what it has already checked so it does not have to do the same work twice, which makes the whole process much faster. Once the helper has counted all the special towers up to the biggest number and subtracted the ones that are too small, it knows exactly how many special numbers exist in that range. It is basically just sorting through piles of numbers to count only the ones that follow the special stair-step pattern.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality