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 thestepping 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.
C++#
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
}
|
Java#
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;
}
}
|
Kotlin#
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
}
}
|
Python#
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
|
Rust#
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
}
}
|
TypeScript#
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.