1215. Stepping Numbers

Stepping Numbers is a representative generate rather than scan problem that is commonly solved using BFS or DFS. It evaluates your ability to identify a simple local constraint (adjacent digits must differ by exactly 1) and convert it into a systematic state-expansion approach with effective pruning. This strengthens the same core skill used in many interview questions: generating only valid candidates efficiently instead of brute-forcing a large search space.

Problem statement

You’re given two integers low and high. Your task is to return a sorted list of all integers in the inclusive range [low, high] that are stepping numbers.

A stepping number is an integer where every pair of adjacent digits differs by exactly 1. For example:

• 123 is a stepping number (1↔2, 2↔3 differ by 1).
• 124 is not a stepping number (1↔2 differ by 1 but 2↔4 differ by 2).
• 10 is stepping (1 and 0 differ by 1).
• Single-digit numbers (like 0, 7) count as stepping numbers.

Constraints:

• 0 <= low <= high <= 2 x 10⁹

Examples

Naive approach

A simple way is to iterate over every number from low to high and check if it’s a stepping number by comparing adjacent digits (each pair must differ by exactly 1). This is easy to implement, but it can be very slow when the range is large because you may end up validating a huge amount of numbers even though only a small fraction are stepping numbers.

Key observation

Stepping numbers follow a very strict digit pattern, which makes them easy to generate instead of brute-checking every value in the range. If a stepping number ends in digit d, then the next digit we append can only be d – 1 (when d > 0) or d + 1 (when d < 9). This means every stepping number can be built digit-by-digit, and every generated number is guaranteed to remain valid.

Optimized approach using BFS

We use a queue (BFS) to build stepping numbers instead of checking every number in the range. We start by putting 0 to 9 in the queue because every single-digit number is already a stepping number. Then we repeatedly take a number x out of the queue:

• If x is inside [low, high], we add it to our answer.
• If x is bigger than high, we ignore it (and don’t expand it further).
• If x is 0, we also don’t expand it, because expanding 0 would create numbers like 01, which are not valid normal integers (they have a leading zero).

For any other number, we look at its last digit d. The next stepping numbers can only be made by adding one more digit at the end: d – 1 and/or d + 1 (only if they stay between 0 and 9). We push those new numbers into the queue, but only if they are <= high so we don’t to avoid extra processing. At the end, because the order we discover numbers in BFS is not always sorted, we sort the result list before returning it.

Step-by-step algorithm

The algorithm works in these steps:

1. Initialize an empty list result to store stepping numbers in the range, and a queue q for BFS.
2. Push all single-digit numbers 0 to 9 into q (every single-digit number is a stepping number).
3. While q is not empty:
   1. Pop the front number x from the queue.
   2. If x is greater than high, skip it (and do not expand it).
   3. If x lies within [low, high], append it to result.
   4. If x is 0, continue without expanding (to avoid creating numbers like 01).
   5. Let last = x % 10 be the last digit of x.
   6. If last > 0, create nxt = x * 10 + (last - 1) and push it into q if nxt <= high.
   7. If last < 9, create nxt = x * 10 + (last + 1) and push it into q if nxt <= high.
4. Sort result (because BFS generation order is not guaranteed to be increasing).
5. Return the result.

The slides below help to visualize the solution better.

1 / 7

Python implementation for the optimal solution

Here’s the Python code for the optimized solution using BFS.

from collections import deque

def countSteppingNumbers(low, high):
    result: List[int] = []
    q = deque()

    # 1) Seed BFS with all single-digit numbers (0 to 9).
    #    Single-digit numbers are always stepping numbers.
    for d in range(10):
        q.append(d)

    # 2) BFS: each time we pop a number, we try to append a next digit (last_digit ± 1)
    #    to form new stepping numbers.
    while q:
        x = q.popleft()

        # If x is already larger than high, we don't record it and also skip expanding it.
        if x > high:
            continue

        # If x is within range, record it.
        if x >= low:
            result.append(x)

        # Avoid generating numbers with leading zeros like 01, 012, etc.
        # So we do not expand from 0.
        if x == 0:
            continue

        last = x % 10

        # 3) If last digit > 0, we can append (last - 1)
        if last > 0:
            nxt = x * 10 + (last - 1)
            if nxt <= high:          # pruning: no need to push larger than high
                q.append(nxt)

        # 4) If last digit < 9, we can append (last + 1)
        if last < 9:
            nxt = x * 10 + (last + 1)
            if nxt <= high:          # pruning
                q.append(nxt)

    # 5) BFS does not guarantee sorted output, so sort at the end.
    result.sort()
    return result


# Driver code
def main():
    test_cases = [
        (0, 31),      # expected [0,1,2,3,4,5,6,7,8,9,10,12,21,23]
        (10, 25),     # expected [10,12,21,23]
        (98, 102),    # expected [98,101]
        (120, 132),   # expected [121,123]
        (500, 550),   # expected [543,545]
    ]

    for idx, (low, high) in enumerate(test_cases, 1):
        output = countSteppingNumbers(low, high)
        print(f"{idx}.\tlow = {low}, high = {high}")
        print(f"\tOutput: {output}")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity 

The BFS generates only valid stepping numbers up to high. If we let K be the total number of stepping numbers generated (and M be how many fall inside [low, high]), the BFS itself takes O(K) time because each generated number is processed once. At the end, we sort the collected results, which takes O(M log M) time, so the overall time complexity is O(K + M log M).

Space complexity

We store generated numbers in the queue during BFS and the final answers in the result list. In the worst case, both can grow proportional to the number of generated stepping numbers, so the space complexity is O(K).

Common mistakes to avoid

To completely prepare this coding problem, keep an eye for the following common mistakes candidates make:

Tree traversal mental model: Visualize the problem as a tree where each node is a digit and branches to its neighbors, which helps justify using BFS or DFS.

Sorting requirement: Remember that BFS generates numbers by digit length, not absolute value, so you must explicitly sort the final list to meet LeetCode’s output requirements.

Memory trade-offs: Be prepared to explain that BFS uses more memory for the queue, while DFS is more space-efficient but carries a risk of recursion depth issues in some languages.