Problem Description

Given two integers low and high, return a list of all the Stepping Numbers in the inclusive range [low, high].

A Stepping Number is an integer where the absolute difference between every pair of adjacent digits is exactly 1. For example, 321 and 121 are stepping numbers, but 421 is not (since |4-2| = 2).

The result should be sorted in increasing order.

Constraints:

• 0 <= low <= high <= 2 * 10^9
• The answer may contain multiple numbers.

Thought Process

At first glance, it seems we could check every number between low and high to see if it's a stepping number. However, this is impractical because the range could be huge (up to 2 billion), making brute-force solutions too slow.

Instead, we notice that stepping numbers have a special property: each digit is determined by the previous digit (must be either +1 or -1). This allows us to generate stepping numbers directly, rather than checking all numbers.

We can think of building each stepping number digit by digit, starting from 0 to 9, and for each, recursively or iteratively appending digits that are one more or one less than the previous digit. This is similar to a breadth-first search (BFS) or depth-first search (DFS) on possible numbers.

Solution Approach

We can use a BFS approach to efficiently generate all stepping numbers in the range. Here's how:

1. Initialize a queue: Start by enqueuing each digit from 0 to 9. (We include 0 because 0 itself is a stepping number if the range allows.)
2. Process numbers in the queue: For each number, if it's within [low, high], add it to the result.
3. Expand stepping numbers: For each number, get its last digit. You can append a digit last_digit - 1 and last_digit + 1 (as long as the result is a valid digit 0-9), and form new numbers by adding these digits to the end. Enqueue these new numbers if they are less than or equal to high.
4. Repeat: Continue until the queue is empty.
5. Sort and return: Collect all valid stepping numbers in a result list, sort it, and return.

• 0 is a valid stepping number only if low == 0.
• We avoid numbers with unnecessary leading zeros.

Example Walkthrough

Example:
low = 10, high = 21

Step 1: Start BFS from digits 1 to 9 (we can skip 0 since 0 < 10).
Step 2: For each number, expand by appending digits:

• Start with 1: last digit is 1. Possible next digits: 0 and 2.
  - 10 (1*10+0), 12 (1*10+2)
• Start with 2: last digit is 2. Next: 1 and 3.
  - 21 (2*10+1), 23 (2*10+3)
• Continue similarly for 3-9.

Time and Space Complexity

Brute-force approach:

• Time: O(high - low) — Too slow for large ranges.
• Space: O(1) or O(n) for results.

• Time: O(N), where N is the number of stepping numbers in the range. Each stepping number is generated once.
• Space: O(N) for the queue and result list.

Summary

The Stepping Numbers problem leverages digit adjacency properties to avoid brute-force checking. Using BFS, we efficiently generate all valid stepping numbers in a given range by expanding from each digit and only appending valid next digits. This approach is both elegant and efficient, as it directly constructs candidates and avoids unnecessary work. The result is a sorted list of stepping numbers within the specified range.

Code Implementation

from collections import deque

def steppingNumbers(low, high):
    result = []
    if low == 0:
        result.append(0)
    queue = deque(range(1, 10))
    while queue:
        num = queue.popleft()
        if num > high:
            continue
        if num >= low:
            result.append(num)
        last_digit = num % 10
        # Append next possible digits
        for next_digit in [last_digit - 1, last_digit + 1]:
            if 0 <= next_digit <= 9:
                next_num = num * 10 + next_digit
                if next_num <= high:
                    queue.append(next_num)
    return sorted(result)
      

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> steppingNumbers(int low, int high) {
    vector<int> result;
    if (low == 0) result.push_back(0);
    queue<int> q;
    for (int i = 1; i <= 9; ++i) q.push(i);

    while (!q.empty()) {
        int num = q.front(); q.pop();
        if (num > high) continue;
        if (num >= low) result.push_back(num);

        int last_digit = num % 10;
        if (last_digit > 0) {
            int next_num = num * 10 + (last_digit - 1);
            if (next_num <= high) q.push(next_num);
        }
        if (last_digit < 9) {
            int next_num = num * 10 + (last_digit + 1);
            if (next_num <= high) q.push(next_num);
        }
    }
    sort(result.begin(), result.end());
    return result;
}
      

import java.util.*;

public class Solution {
    public List<Integer> steppingNumbers(int low, int high) {
        List<Integer> result = new ArrayList<>();
        if (low == 0) result.add(0);
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 9; i++) queue.offer(i);

        while (!queue.isEmpty()) {
            int num = queue.poll();
            if (num > high) continue;
            if (num >= low) result.add(num);

            int lastDigit = num % 10;
            if (lastDigit > 0) {
                int nextNum = num * 10 + (lastDigit - 1);
                if (nextNum <= high) queue.offer(nextNum);
            }
            if (lastDigit < 9) {
                int nextNum = num * 10 + (lastDigit + 1);
                if (nextNum <= high) queue.offer(nextNum);
            }
        }
        Collections.sort(result);
        return result;
    }
}
      

function steppingNumbers(low, high) {
    let result = [];
    if (low === 0) result.push(0);
    let queue = [];
    for (let i = 1; i <= 9; i++) queue.push(i);

    while (queue.length > 0) {
        let num = queue.shift();
        if (num > high) continue;
        if (num >= low) result.push(num);
        let lastDigit = num % 10;
        if (lastDigit > 0) {
            let nextNum = num * 10 + (lastDigit - 1);
            if (nextNum <= high) queue.push(nextNum);
        }
        if (lastDigit < 9) {
            let nextNum = num * 10 + (lastDigit + 1);
            if (nextNum <= high) queue.push(nextNum);
        }
    }
    result.sort((a, b) => a - b);
    return result;
}