Problem Description

A stepping number is a special type of integer where every pair of adjacent digits differs by exactly 1.

For example:

• 321 is a stepping number because: 3→2 differs by 1, and 2→1 differs by 1
• 421 is not a stepping number because: 4→2 differs by 2

Given two integers low and high, you need to find all stepping numbers within the range [low, high] (inclusive) and return them as a sorted list.

The solution uses a BFS (Breadth-First Search) approach. It starts by handling the special case where 0 might be in the range (since 0 is considered a stepping number). Then it initializes a queue with single-digit numbers 1 through 9 (all single-digit numbers are stepping numbers).

The algorithm works by:

1. Taking a number v from the queue
2. If v exceeds high, stop the search
3. If v is within [low, high], add it to the answer
4. Generate new stepping numbers by appending valid digits to v:
   • Get the last digit x of v
   • If x > 0, append x-1 to create v * 10 + (x-1)
   • If x < 9, append x+1 to create v * 10 + (x+1)
5. Add these new numbers to the queue for further processing

This approach ensures all stepping numbers are generated in increasing order, automatically providing a sorted result.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: While we can think of stepping numbers as forming a tree-like structure where each number can generate new numbers, the problem itself isn't explicitly about graph nodes and edges.

Need to solve for kth smallest/largest?

• No: We need to find all stepping numbers in a range, not the kth smallest/largest.

Involves Linked Lists?

• No: The problem doesn't involve linked list data structures.

Does the problem have small constraints?

• No: The constraints can be quite large (up to 10^9 typically), and we need an efficient approach rather than pure brute force. However, the branching factor is limited - each digit can only generate at most 2 new digits (±1).

BFS?

• Yes: BFS is the appropriate choice here because:
  1. We're generating numbers level by level (1-digit, then 2-digit, then 3-digit, etc.)
  2. We want to explore all possibilities at each "depth" before moving deeper
  3. The queue-based approach naturally generates numbers in ascending order
  4. We can stop early when we exceed the high boundary

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for systematically generating stepping numbers. Starting from single digits (1-9), we expand each number by appending valid adjacent digits (last digit ±1), exploring all numbers of the same length before moving to longer numbers. This ensures we find all stepping numbers in the given range efficiently.

Intuition

Think about how stepping numbers are constructed - each digit must differ from its neighbor by exactly 1. This means if we have a stepping number, we can generate new stepping numbers by appending valid digits to it.

Starting with a stepping number like 12, we can only append 1 or 3 to maintain the stepping property (since the last digit is 2, the next digit must be 2±1). This gives us 121 and 123.

This generation process naturally forms a tree structure:

• Root: single digits 1-9 (all are stepping numbers)
• Children: generated by appending valid digits

The key insight is that we want to explore this tree level by level (BFS) rather than depth-first because:

1. Natural ordering: BFS explores all n-digit numbers before moving to (n+1)-digit numbers, which means we generate numbers in ascending order
2. Early termination: Once we generate a number larger than high, we know all subsequent numbers at that level and deeper will also exceed high
3. Systematic generation: Using a queue ensures we don't miss any stepping numbers and don't generate duplicates

The algorithm mimics building numbers digit by digit. For each stepping number in our queue:

• Extract its last digit x
• If x > 0, we can append x-1 (multiply by 10 and add x-1)
• If x < 9, we can append x+1 (multiply by 10 and add x+1)

This way, every stepping number acts as a "seed" to generate longer stepping numbers, and the BFS approach ensures we find them all in the desired range efficiently.

Learn more about Breadth-First Search, Math and Backtracking patterns.

Solution Approach

The implementation uses BFS with a queue to systematically generate all stepping numbers in the range [low, high].

Initial Setup:

• Create an empty list ans to store results
• Handle the special case: if low == 0, add 0 to the answer (since 0 is considered a stepping number)
• Initialize a queue with all single-digit numbers 1 through 9 using deque(range(1, 10))

BFS Process: The main loop continues while the queue is not empty:

1. Extract and Check: Pop the leftmost element v from the queue

   • If v > high, break immediately (all subsequent numbers will be larger)
   • If v >= low, add it to the answer list

2. Generate New Numbers: Based on the last digit x of current number v:

   • Extract last digit: x = v % 10
   • If x > 0: Create new number by appending x-1: v * 10 + x - 1
   • If x < 9: Create new number by appending x+1: v * 10 + x + 1
   • Add these new numbers to the queue for future processing

Why This Works:

• The queue processes numbers in increasing order (all n-digit numbers before (n+1)-digit numbers)
• Each number generates at most 2 new stepping numbers
• The condition v > high ensures we stop as soon as we exceed the range
• The condition x > 0 and x < 9 prevents invalid digits (no negative digits or digits > 9)

Example Trace: For range [10, 20]:

• Queue starts with: [1, 2, 3, ..., 9]
• Process 1: generates 10 and 12 → add both to queue
• Process 2: generates 21 and 23 → add to queue (but 21 > 20, so we'd stop)
• 10 and 12 are within range, so they're added to answer

The algorithm naturally produces a sorted result since BFS explores numbers level by level in ascending order.

Example Walkthrough

Let's trace through finding all stepping numbers in the range [10, 25].

Initial Setup:

• ans = [] (empty result list)
• Since low = 10 ≠ 0, we don't add 0
• Queue initialized with: [1, 2, 3, 4, 5, 6, 7, 8, 9]

BFS Processing:

Round 1: Process v = 1

• v = 1 < low, so don't add to answer
• Last digit x = 1
• Since x > 0: generate 1 * 10 + (1-1) = 10 → add to queue
• Since x < 9: generate 1 * 10 + (1+1) = 12 → add to queue
• Queue now: [2, 3, 4, 5, 6, 7, 8, 9, 10, 12]

Round 2: Process v = 2

• v = 2 < low, so don't add to answer
• Last digit x = 2
• Since x > 0: generate 2 * 10 + (2-1) = 21 → add to queue
• Since x < 9: generate 2 * 10 + (2+1) = 23 → add to queue
• Queue now: [3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23]

Rounds 3-9: Process v = 3 through v = 9

• All are < low, so none added to answer
• Each generates two new numbers added to queue

Round 10: Process v = 10

• v = 10 >= low, so add 10 to answer: ans = [10]
• Last digit x = 0
• Since x = 0 (not > 0): can't generate with x-1
• Since x < 9: generate 10 * 10 + (0+1) = 101 → add to queue

Round 11: Process v = 12

• v = 12 >= low, so add 12 to answer: ans = [10, 12]
• Last digit x = 2
• Since x > 0: generate 12 * 10 + (2-1) = 121 → add to queue
• Since x < 9: generate 12 * 10 + (2+1) = 123 → add to queue

Round 12: Process v = 21

• v = 21 >= low, so add 21 to answer: ans = [10, 12, 21]
• Last digit x = 1
• Since x > 0: generate 21 * 10 + (1-1) = 210 → add to queue
• Since x < 9: generate 21 * 10 + (1+1) = 212 → add to queue

Round 13: Process v = 23

• v = 23 >= low, so add 23 to answer: ans = [10, 12, 21, 23]
• Last digit x = 3
• Since x > 0: generate 23 * 10 + (3-1) = 232 → add to queue
• Since x < 9: generate 23 * 10 + (3+1) = 234 → add to queue

Round 14: Process v = 32

• v = 32 > high = 25, so break the loop

Final Result: [10, 12, 21, 23]

All numbers in our answer are stepping numbers:

• 10: 1→0 differs by 1 ✓
• 12: 1→2 differs by 1 ✓
• 21: 2→1 differs by 1 ✓
• 23: 2→3 differs by 1 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(10 × 2^(log M)), where M is the value of high. This can be understood as follows:

• The algorithm uses BFS to generate all stepping numbers starting from single digits 1-9
• Each stepping number can branch into at most 2 new stepping numbers (by appending either last_digit - 1 or last_digit + 1)
• The maximum depth of this tree is approximately log₁₀(high) (the number of digits in high)
• At each level d, there can be at most 9 × 2^(d-1) stepping numbers
• The total number of stepping numbers processed is bounded by O(9 × (2^0 + 2^1 + ... + 2^(log M - 1))) = O(9 × 2^(log M)) ≈ O(10 × 2^(log M))

The space complexity is O(2^(log M)), where M is the value of high. This is because:

• The queue q stores stepping numbers during BFS traversal
• In the worst case, the queue can hold up to O(2^(log M)) stepping numbers at once (when processing numbers with maximum digits)
• The answer list ans also stores up to O(2^(log M)) stepping numbers in the range [low, high]
• Therefore, the total space complexity is O(2^(log M))

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Queue Initialization Order

A common mistake is initializing the queue incorrectly or processing numbers in the wrong order, which can lead to unsorted results or missing numbers.

Pitfall Example:

# Wrong: Using a different data structure or wrong initialization
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # Using list instead of deque
# Or initializing with wrong order/values
queue = deque([9, 8, 7, 6, 5, 4, 3, 2, 1])  # Reverse order

Solution: Always use deque(range(1, 10)) to ensure proper BFS traversal. The deque ensures O(1) append and popleft operations, and the correct order ensures numbers are processed in ascending order.

2. Forgetting to Handle Zero as a Special Case

Zero is a valid stepping number but cannot be generated through the BFS process since we start with digits 1-9.

Pitfall Example:

def countSteppingNumbers(self, low: int, high: int) -> List[int]:
    result = []
    # Missing: if low == 0: result.append(0)
    queue = deque(range(1, 10))
    # ... rest of code

Solution: Always check if low == 0 at the beginning and add 0 to the result if true. Alternatively, check if low <= 0 <= high for a more explicit range check.

3. Breaking Too Early or Too Late

The break condition if current_number > high must be placed correctly to avoid missing valid numbers or processing unnecessary ones.

Pitfall Example:

while queue:
    current_number = queue.popleft()
  
    if current_number >= low:
        result.append(current_number)
  
    # Wrong: Breaking after adding to result might miss valid numbers
    if current_number > high:
        break
  
    # Generate next numbers...

Solution: Place the break immediately after popping from queue and before checking if the number should be added to results. This ensures we don't add numbers > high but also don't miss valid numbers in the queue.

4. Generating Invalid Next Numbers

When appending digits, failing to check boundaries can create invalid stepping numbers or cause errors.

Pitfall Example:

last_digit = current_number % 10

# Wrong: Not checking if last_digit - 1 is valid
next_number = current_number * 10 + last_digit - 1
queue.append(next_number)  # Could append number ending in -1

# Wrong: Not checking if last_digit + 1 is valid
next_number = current_number * 10 + last_digit + 1
queue.append(next_number)  # Could append number ending in 10

Solution: Always validate:

• Only append (last_digit - 1) when last_digit > 0
• Only append (last_digit + 1) when last_digit < 9

5. Overflow for Large Ranges

For very large values of high, the generated numbers might exceed integer limits or cause memory issues with a huge queue.

Pitfall Example:

# If high is near MAX_INT, multiplication by 10 could overflow
next_number = current_number * 10 + last_digit + 1
# No check for potential overflow

Solution: Add a check before appending to queue:

if last_digit < 9:
    next_number = current_number * 10 + last_digit + 1
    if next_number <= high:  # Additional safety check
        queue.append(next_number)

This prevents adding numbers to the queue that would exceed the range, improving both safety and efficiency.