Stepping Numbers

medium math bfs number theory

Problem

A stepping number is an integer where all of its adjacent digits differ by exactly 1. For example, 321 is a stepping number while 421 is not. Given two integers low and high, return a sorted list of all stepping numbers in the inclusive range [low, high]. Single-digit numbers (0–9) are stepping numbers.

Inputlow = 0, high = 21

Output[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21]

10 (1→0 differ by 1), 12 (1→2) and 21 (2→1) qualify; 11 does not because 1→1 differs by 0.

low

high

from collections import deque

def stepping_numbers(low, high):
    res = []
    if low == 0:
        res.append(0)
    queue = deque(range(1, 10))
    while queue:
        num = queue.popleft()
        if num > high:
            continue
        if num >= low:
            res.append(num)
        last = num % 10
        if last > 0:
            queue.append(num * 10 + last - 1)
        if last < 9:
            queue.append(num * 10 + last + 1)
    return sorted(res)

function steppingNumbers(low, high) {
  const res = [];
  if (low === 0) res.push(0);
  const queue = [1, 2, 3, 4, 5, 6, 7, 8, 9];
  while (queue.length) {
    const num = queue.shift();
    if (num > high) continue;
    if (num >= low) res.push(num);
    const last = num % 10;
    if (last > 0) queue.push(num * 10 + last - 1);
    if (last < 9) queue.push(num * 10 + last + 1);
  }
  return res.sort((a, b) => a - b);
}

class Solution {
    public List<Integer> steppingNumbers(int low, int high) {
        List<Integer> res = new ArrayList<>();
        if (low == 0) res.add(0);
        Queue<Long> queue = new LinkedList<>();
        for (int d = 1; d <= 9; d++) queue.add((long) d);
        while (!queue.isEmpty()) {
            long num = queue.poll();
            if (num > high) continue;
            if (num >= low) res.add((int) num);
            long last = num % 10;
            if (last > 0) queue.add(num * 10 + last - 1);
            if (last < 9) queue.add(num * 10 + last + 1);
        }
        Collections.sort(res);
        return res;
    }
}

vector<int> steppingNumbers(int low, int high) {
    vector<int> res;
    if (low == 0) res.push_back(0);
    queue<long> q;
    for (int d = 1; d <= 9; d++) q.push(d);
    while (!q.empty()) {
        long num = q.front(); q.pop();
        if (num > high) continue;
        if (num >= low) res.push_back((int) num);
        long last = num % 10;
        if (last > 0) q.push(num * 10 + last - 1);
        if (last < 9) q.push(num * 10 + last + 1);
    }
    sort(res.begin(), res.end());
    return res;
}

Explanation

A stepping number is one where each digit sits exactly one apart from the digit beside it, like 123 or 321. Instead of testing every number in the range, we grow stepping numbers digit by digit so we only ever touch valid ones.

The trick is to notice that if a number is stepping, you can extend it by appending a digit that is either one more or one less than its last digit. So we use a queue (BFS): seed it with the single digits 1..9, then repeatedly pop a number and push its valid children.

For a popped number num, the last digit is last = num % 10. If last > 0 we push num*10 + last-1; if last < 9 we push num*10 + last+1. Any number that lands in [low, high] is collected, and once a number passes high we skip it because its children are only bigger.

Example: pop 1. Its last digit is 1, so it spawns 10 and 12. Pop 2 and it spawns 21 and 23. That is exactly how 10, 12, and 21 show up in the range [0, 21].

Because we only ever build numbers that stay stepping, we generate just the answers (plus a few that overshoot), then sort them at the end.

Time: O(k log k) Space: O(k)