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].

Examples

Example 1:

1
2
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]

Example 2:

1
2
Input: low = 10, high = 15
Output: [10,12]

Constraints:

0 <= low <= high <= 2 * 109

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

We can generate stepping numbers by starting from each digit (0-9) and appending digits that differ by 1 from the last digit. BFS ensures we generate numbers in increasing order and avoid duplicates. This approach is efficient for the given range.

Approach

Start BFS from each digit 0-9.
For each number, if it is within [low, high], add to the answer.
For each number, append next possible digits (last digit ±1) to form new numbers, and continue BFS if within range.
Return the sorted list of valid stepping numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        if (low == 0) ans.push_back(0);
        for (int i = 1; i <= 9; ++i) {
            queue<long long> q;
            q.push(i);
            while (!q.empty()) {
                long long num = q.front(); q.pop();
                if (num > high) continue;
                if (num >= low) ans.push_back((int)num);
                int last = num % 10;
                if (last > 0) q.push(num * 10 + (last - 1));
                if (last < 9) q.push(num * 10 + (last + 1));
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func countSteppingNumbers(low int, high int) []int {
    ans := []int{}
    if low == 0 {
        ans = append(ans, 0)
    }
    for i := 1; i <= 9; i++ {
        q := []int{i}
        for len(q) > 0 {
            num := q[0]
            q = q[1:]
            if num > high {
                continue
            }
            if num >= low {
                ans = append(ans, num)
            }
            last := num % 10
            if last > 0 {
                next := num*10 + (last-1)
                if next <= high {
                    q = append(q, next)
                }
            }
            if last < 9 {
                next := num*10 + (last+1)
                if next <= high {
                    q = append(q, next)
                }
            }
        }
    }
    sort.Ints(ans)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> countSteppingNumbers(int low, int high) {
        List<Integer> ans = new ArrayList<>();
        if (low == 0) ans.add(0);
        for (int i = 1; i <= 9; ++i) {
            Queue<Long> q = new LinkedList<>();
            q.offer((long)i);
            while (!q.isEmpty()) {
                long num = q.poll();
                if (num > high) continue;
                if (num >= low) ans.add((int)num);
                int last = (int)(num % 10);
                if (last > 0) q.offer(num * 10 + (last - 1));
                if (last < 9) q.offer(num * 10 + (last + 1));
            }
        }
        Collections.sort(ans);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun countSteppingNumbers(low: Int, high: Int): List<Int> {
        val ans = mutableListOf<Int>()
        if (low == 0) ans.add(0)
        for (i in 1..9) {
            val q = ArrayDeque<Long>()
            q.add(i.toLong())
            while (q.isNotEmpty()) {
                val num = q.removeFirst()
                if (num > high) continue
                if (num >= low) ans.add(num.toInt())
                val last = num % 10
                if (last > 0) q.add(num * 10 + (last - 1))
                if (last < 9) q.add(num * 10 + (last + 1))
            }
        }
        ans.sort()
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def countSteppingNumbers(self, low: int, high: int) -> list[int]:
        ans: list[int] = []
        if low == 0:
            ans.append(0)
        for i in range(1, 10):
            q = [i]
            while q:
                num = q.pop(0)
                if num > high:
                    continue
                if num >= low:
                    ans.append(num)
                last = num % 10
                if last > 0:
                    next_num = num * 10 + (last - 1)
                    if next_num <= high:
                        q.append(next_num)
                if last < 9:
                    next_num = num * 10 + (last + 1)
                    if next_num <= high:
                        q.append(next_num)
        ans.sort()
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn count_stepping_numbers(low: i32, high: i32) -> Vec<i32> {
        let mut ans = Vec::new();
        if low == 0 {
            ans.push(0);
        }
        for i in 1..=9 {
            let mut q = std::collections::VecDeque::new();
            q.push_back(i as i64);
            while let Some(num) = q.pop_front() {
                if num > high as i64 { continue; }
                if num >= low as i64 { ans.push(num as i32); }
                let last = num % 10;
                if last > 0 {
                    let next = num * 10 + (last - 1);
                    if next <= high as i64 {
                        q.push_back(next);
                    }
                }
                if last < 9 {
                    let next = num * 10 + (last + 1);
                    if next <= high as i64 {
                        q.push_back(next);
                    }
                }
            }
        }
        ans.sort();
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    countSteppingNumbers(low: number, high: number): number[] {
        const ans: number[] = [];
        if (low === 0) ans.push(0);
        for (let i = 1; i <= 9; ++i) {
            const q: number[] = [i];
            while (q.length) {
                const num = q.shift()!;
                if (num > high) continue;
                if (num >= low) ans.push(num);
                const last = num % 10;
                if (last > 0) {
                    const next = num * 10 + (last - 1);
                    if (next <= high) q.push(next);
                }
                if (last < 9) {
                    const next = num * 10 + (last + 1);
                    if (next <= high) q.push(next);
                }
            }
        }
        ans.sort((a, b) => a - b);
        return ans;
    }
}

Complexity

⏰ Time complexity: O(log(high) * 9 * D) — Each number is generated once, D is the number of digits in high.
🧺 Space complexity: O(N) — N is the number of stepping numbers generated.

Problem#

Examples#

Solution#

Method 1 – Breadth-First Search (BFS)#

Intuition#

Approach#

Code#

Complexity#