Skip to content

1215. Stepping Numbers πŸ”’

Description

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

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Solutions

Solution 1: BFS

Thinking

\(high\) can be \(2\times 10^9\), so testing every integer is impossible. A stepping number's next digit is only last-digit \(\pm 1\), so we grow them from \(1\sim 9\) by BFS; the count is far smaller than the value range.

The queue is increasing; we stop past \(high\) and keep values in \([low,high]\). Zero is handled separately. BFS both emits in order and avoids duplicates.

First, if \(low\) is \(0\), we need to add \(0\) to the answer.

Next, we create a queue \(q\) and add \(1 \sim 9\) to the queue. Then, we repeatedly take out elements from the queue. Let the current element be \(v\). If \(v\) is greater than \(high\), we stop searching. If \(v\) is in the range \([low, high]\), we add \(v\) to the answer. Then, we need to record the last digit of \(v\) as \(x\). If \(x \gt 0\), we add \(v \times 10 + x - 1\) to the queue. If \(x \lt 9\), we add \(v \times 10 + x + 1\) to the queue. Repeat the above steps until the queue is empty.

The time complexity is \(O(10 \times 2^{\log M})\), and the space complexity is \(O(2^{\log M})\), where \(M\) is the number of digits in \(high\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
        ans = []
        if low == 0:
            ans.append(0)
        q = deque(range(1, 10))
        while q:
            v = q.popleft()
            if v > high:
                break
            if v >= low:
                ans.append(v)
            x = v % 10
            if x:
                q.append(v * 10 + x - 1)
            if x < 9:
                q.append(v * 10 + x + 1)
        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
class Solution {
    public List<Integer> countSteppingNumbers(int low, int high) {
        List<Integer> ans = new ArrayList<>();
        if (low == 0) {
            ans.add(0);
        }
        Deque<Long> q = new ArrayDeque<>();
        for (long i = 1; i < 10; ++i) {
            q.offer(i);
        }
        while (!q.isEmpty()) {
            long v = q.pollFirst();
            if (v > high) {
                break;
            }
            if (v >= low) {
                ans.add((int) v);
            }
            int x = (int) v % 10;
            if (x > 0) {
                q.offer(v * 10 + x - 1);
            }
            if (x < 9) {
                q.offer(v * 10 + x + 1);
            }
        }
        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
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        if (low == 0) {
            ans.push_back(0);
        }
        queue<long long> q;
        for (int i = 1; i < 10; ++i) {
            q.push(i);
        }
        while (!q.empty()) {
            long long v = q.front();
            q.pop();
            if (v > high) {
                break;
            }
            if (v >= low) {
                ans.push_back(v);
            }
            int x = v % 10;
            if (x > 0) {
                q.push(v * 10 + x - 1);
            }
            if (x < 9) {
                q.push(v * 10 + x + 1);
            }
        }
        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
func countSteppingNumbers(low int, high int) []int {
    ans := []int{}
    if low == 0 {
        ans = append(ans, 0)
    }
    q := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    for len(q) > 0 {
        v := q[0]
        q = q[1:]
        if v > high {
            break
        }
        if v >= low {
            ans = append(ans, v)
        }
        x := v % 10
        if x > 0 {
            q = append(q, v*10+x-1)
        }
        if x < 9 {
            q = append(q, v*10+x+1)
        }
    }
    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
function countSteppingNumbers(low: number, high: number): number[] {
    const ans: number[] = [];
    if (low === 0) {
        ans.push(0);
    }
    const q: number[] = [];
    for (let i = 1; i < 10; ++i) {
        q.push(i);
    }
    while (q.length) {
        const v = q.shift()!;
        if (v > high) {
            break;
        }
        if (v >= low) {
            ans.push(v);
        }
        const x = v % 10;
        if (x > 0) {
            q.push(v * 10 + x - 1);
        }
        if (x < 9) {
            q.push(v * 10 + x + 1);
        }
    }
    return ans;
}

Comments