Stepping Numbers - Practice Coding Problems

Stepping Numbers - Problem

A stepping number is an integer such that all of its adjacent digits have an absolute difference of 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 the stepping numbers in the inclusive range [low, high].

Input & Output

Example 1 — Basic Range

$ Input: low = 0, high = 21

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

💡 Note: All single digits 0-9 are stepping numbers. For two digits: 10 (|1-0|=1), 12 (|1-2|=1), and 21 (|2-1|=1) are valid. Numbers like 11, 13, 14, etc. are invalid as adjacent digits don't differ by 1.

Example 2 — Higher Range

$ Input: low = 10, high = 15

› Output: [10,12]

💡 Note: In range [10,15]: 10 has digits 1,0 with |1-0|=1 ✓. 12 has digits 1,2 with |1-2|=1 ✓. Numbers 11,13,14,15 don't satisfy the stepping property.

Example 3 — Single Range

$ Input: low = 90, high = 101

› Output: [101]

💡 Note: Only 101 is a stepping number in this range: digits 1,0,1 have differences |1-0|=1 and |0-1|=1, both equal to 1.

Constraints

0 ≤ low ≤ high ≤ 2 × 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given range [0, 21] to find stepping numbers

Check Property

Adjacent digits must differ by exactly 1

Valid Numbers

Collect all numbers satisfying the property

Key Takeaway

🎯 Key Insight: Generate stepping numbers by extending valid prefixes rather than checking all numbers

Asked in

G Google 45 a Amazon 35 M Microsoft 28

The key insight is that stepping numbers can be efficiently generated by starting from single digits and extending them by appending digits that differ by exactly 1. Best approach uses BFS or DFS to generate only valid numbers rather than checking all numbers in range. Time: O(2^d), Space: O(2^d) for BFS or O(d) for DFS where d is the number of digits.

Common Approaches

Approach	Time	Space	Notes
✓ BFS - Level by Level Generation	O(2^d)	O(2^d)	Build stepping numbers level by level using breadth-first search
Brute Force - Check Every Number	O(n × d)	O(1)	Check each number in range to see if it's a stepping number
DFS - Recursive Generation	O(2^d)	O(d)	Use depth-first search to recursively build stepping numbers

BFS - Level by Level Generation — Algorithm Steps

Initialize queue with single digit numbers 0-9
For each number, try appending digit±1 to form new stepping numbers
Filter results within the given range

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Queue

Initialize with digits 0-9

Extend Numbers

Append ±1 digits to each number

Filter Range

Keep only numbers in [low,high]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    long long data[10000];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

void enqueue(Queue* q, long long val) {
    q->data[q->rear++] = val;
}

long long dequeue(Queue* q) {
    return q->data[q->front++];
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int low, high;
    scanf("%d %d", &low, &high);
    
    Queue q;
    initQueue(&q);
    int result[1000];
    int count = 0;
    
    // Start with single digits 0-9
    for (int i = 0; i <= 9; i++) {
        enqueue(&q, i);
    }
    
    while (!isEmpty(&q)) {
        long long num = dequeue(&q);
        
        if (num > high) continue;
        
        if (num >= low) {
            result[count++] = num;
        }
        
        if (num == 0) continue;  // Don't extend 0
        
        int lastDigit = num % 10;
        
        // Try appending digit-1
        if (lastDigit > 0) {
            long long nextNum = num * 10 + (lastDigit - 1);
            if (nextNum <= high) {
                enqueue(&q, nextNum);
            }
        }
        
        // Try appending digit+1
        if (lastDigit < 9) {
            long long nextNum = num * 10 + (lastDigit + 1);
            if (nextNum <= high) {
                enqueue(&q, nextNum);
            }
        }
    }
    
    qsort(result, count, sizeof(int), compare);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("%d", result[i]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^d)

Each digit has at most 2 choices (±1), d is max digits in range

✓ Linear Growth

Space Complexity

O(2^d)

Queue stores all stepping numbers being generated

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS - Level by Level Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler